# Dynamic Cost-Aware Routing of Web Requests
## 4 Routing with Learning Automata  
To better explain the proposed method, we first provide a brief overview of how Learning Automata can be applied to a routing problem. A Learning Automaton (LA) is an autonomous decision-making entity that learns to make decisions so as to bring optimal performance in the environment in which it is operating [25; 26]. It implements a specific case of reinforcement learning [27]. An LA makes stochastic selection of an action from the list of available actions and observes its performance; if it sees favorable performance from the selected action, then it increments the selection probability of that action and adjusts the probabilities of other actions; if the selected action produces unfavorable response, then it penalizes the action by decreasing its selection probability. It starts with zero knowledge about the environment and learns on its own to select optimal actions. An action represents a server selection for handling a web request. An automaton is described by a quintuple \(\{\phi,s,X,G,A\}\), where \(X\) is the set of inputs i.e., \(X\in\{0,1\}\); \(\phi\) is the set of internal states \(\{\phi_{1},\phi_{2},...,\phi_{m}\}\); \(s\) is the output set \(\{s_{1},s_{2},...,s_{n}\}\) with \(n\leq m\); \(G:\phi\to s\) denoting the output function and \(A\) is the algorithm that computes the state \(\phi(t+1)\) from state \(\phi(t)\) depending on the response \(X\) it received from the environment. Figure 1 depicts the interaction of LA with its environment.  
The LA are classified as P-model, Q-model and S-model based on the responses it receives from the environment [25]. In P-model LA, the responses from the environment are mapped into binary values 0 and 1; in the Q-model, the responses are mapped into a finite number of values in the interval \([0,1]\) and in the S-model, they are mapped into continuous values in the interval \([0,1]\). The LA are also classified based on the learning parameters used to update the selection probabilities.  
1. **Reward Penalty (RP)**: The learning parameter \(b=a\) and the selection probability of the server is rewarded or penalized equally when the selected server resulted in favorable or unfavorable performance.
2. **Reward Inaction (RI)**: When \(b=0\), there will be no penalty for unfavorable response from the selected server (No action) and the server will be rewarded for favorable response.
3. **Reward Penalty- (RP-e)**: \(b<<a\), the selected action is penalized very little for unfavorable response.  
The constants \(a\) and \(b\) are known as reward and penalty parameters, respectively.  
The LA are broadly classified into fixed structure stochastic automata (FSSA) and variable structure stochastic automata (FSSA). In FSSA, the action probabilities are fixed i.e., transition probabilities are time invariant, whereas, in FSSA, the actions' probabilities are updated based on the performance. The LA are classified as ergodic and non-ergodic according to their Markovian property. The ergodic LA does not lock itself into choosing any one action and it converges with probability distribution independent of initial distribution [28], whereas the non-ergodic LA has absorbing states and converges to an action which has minimum penalty probability with probability 1 [29]. The ergodic LA are suitable for non-stationary environments [28; 30] and non-ergodic LA are apt for stationary environments. Both \(RP\) and \(RP\)-\(e\) have ergodic Markovian properties and \(RI\) has non-ergodic properties. As many works from the literature illustrate the use of ergodic automata in network and communication applications [31; 32; 33; 34; 35; 36; 37], we are inspired to use the S-model Reward  
Figure 1: Stochastic learning automaton.  
Penalty-\(\epsilon\), for making routing decisions in web applications. The servers operating in spatio-temporal electricity market and unpredictable web traffic patterns represent a non-stationary environment and justify the need for a VSSA with ergodic properties.