## 6 Proposed MDP-Based Algorithm  
In this section, we describe our markov decision process (MDP)-based algorithm to obtain the optimal policy of deciding a particular mode for each base station. The following reward function, transition probability and the Value Iteration Algorithm (VIA) are used to solve the optimization problem.  
**Reward:**  
The total reward function for an action, \(a\) is defined as Equation (7)  
\[R(s,a)=\frac{b_{max}-b_{a}}{b_{max}-b_{min}} \tag{7}\]  
where \(b_{a}\) is the total required bandwidth, \(b_{max}\) and \(b_{min}\) are the maximum and minimum required bandwidth respectively. It is noteworthy that the required bandwidth is proportional to the required energy consumption, because less required bandwidth will put more BSs in low power consumption mode, hence would save more energy. Therefore the maximum expected reward from Equation (7) would help us to find the optimal policy in terms of energy efficiency.  
**Transition Probability:**  
The transition probability between two states of the base stations is learned by Monte-Carlo simulation for a particular call arrival rate and death rate. The treatment of the learning part is not within the scope of this paper.  
**Value Iteration Algorithm:**  
If we denote \(V(s)\) as the maximum expected total reward for an initial state \(s\) and future state \(s^{\prime}\) then the optimality equation is given by Equation (8) as follows:  
\[V(s)=max_{a\in A}\{R(s,a)+\sum_{s^{\prime}\in S}\lambda Pr[s^{\prime}|s,a]V(s^ {\prime})\} \tag{8}\]  
Figure 4: Proposed Three-state Markov Model for \(n_{th}\) base station where \(2\leq n\leq N\). (note: The \(1_{st}\) BS is always active).  
Here, \(R(s,a)\) is the reward function for a state \(s\) and action \(a\) as explained in Equation (7); \(Pr[s^{\prime}|s,a]\) is the transition probability between current state \(s\) and future state \(s^{\prime}\) for an action \(a\); \(A\) is the set of all possible actions and \(S\) is the set of all possible states. The solution of the optimality equation correspond to the maximum expected total reward \(V(s)\) and the MDP optimal policy \(\pi(s)\). This MDP optimal policy \(\pi(s)\) indicates the decision of allocating a certain mode to the appropriate base station. As explained in Algorithm 1 value iteration algorithm (VIA) [19] is used to solve this optimization problem.  
```
1:Set \(V^{0}(s^{\prime})=0\) for each state \(s\). Specify \(\zeta>0\), and set \(k=0\).
2:For each state \(s\), compute \(V^{k+1}(s)\) by
3:\(V^{k+1}(s)=max_{a\in A}\{R(s,a)+\sum_{s^{\prime}\in S}\lambda Pr[s^{\prime}|s,a]V^{k}(s^{\prime})\}\)
4:\(\delta=max(V^{k+1}(s)-V^{k}(s))\)
5:If \(\delta<\zeta\frac{1-\lambda}{2\lambda}\), go to step 5.
6:otherwise increase \(k\) by 1 and return to step 2.
7:Output a stationary optimal policy, \(\pi\), such that
8:\(\pi(s)=argmax_{a\in A}\{R(s,a)+\sum_{s^{\prime}\in S}\lambda Pr[s^{\prime}|s,a ]V^{k+1}(s^{\prime})\}\)
9:and stop
```  
**Algorithm 1** Value Iteration Algorithm  
The number of epochs before reaching equilibrium is distributed with mean \(\frac{1}{(1-\lambda)}\) where \(0\leq\lambda<1\); here \(\lambda\) is the discount factor. When expected service duration is known, \(\lambda\) is set accordingly to match the equivalent number of epochs. For example, we have put \(\lambda=0.975\) to model mean service time of 40 epochs.