Introduction

In the previous posts, we have introduced the MDP and its solution. But in practice, we often do not have the simulation of the environment, which means we cannot directly apply our knowledge of MDP to solve the problem. There is indeed a method to simulate the environment, which is called model-based Reinforcement learning. However, in this post, we will focus on the model-free Reinforcement learning, which does not require the simulation of the environment and the construction of MDPs.

Estimating Value Functions

In mode-based RL, value functions can be computed by DP methods as follows:$$\begin{array}{rl}{V}^{\pi }(s)& =E_{\pi }\left[R(s_0,a_0)+\gamma R(s_1,a_1)+{\gamma }^{2}R(s_2,a_2)+\cdots |s_0=s\right]\\ & =R(s,a)+\gamma \sum _{s’}P(s’|s,a)V^{\pi }(s’)\end{array}$$

However, in model-free RL, we cannot directly access the $P(s’|s,a)$ and $R(s,a)$, but we have some ways to estimate the value function from episodes of experience.

Why we estimate the value function?
Because we can use the value function to derive the optimal policy, which is our ultimate goal. Besides value function can help us to reuse historical experience to make better decisions in the future, which is the essence of Reinforcement learning.

Here is a graph to introduce some methods to estimate the value function:

Monte Carlo methods

Target: Learn $V^{\pi }$ from episodes of experience.

Review: accumulate reward function:

$$G_t=R_t+\gamma R_{t+1}+{\gamma }^2{R}_{t+2}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k}$$

Review: value function is the expected return:$$V^{\pi }(s)=E_{\pi }\left[G_t|s_t=s\right]\simeq \frac{1}{N(s)}\sum _{i=1}^{N(s)}{G}_t^i$$
The Monte Carlo method use empirical mean cumulative reward instead of expected return to estimate the value function.

First-visit Monte Carlo method

The first-visit Monte Carlo method estimates the value function by averaging the returns following the first time a state is visited in an episode. The algorithm is as follows:

1. Initialization:
   • For any $s\in S$,$V(s)\in \mathbb{R}$, $N(s)=0$.
   • For any $s\in S$,$\text{returns}(s)=\varnothing$.
2. Loop for each episode:
   • Generate an episode following policy $\pi$: $S_0,A_0,R_1,S_1,A_1,R_2,\cdots ,S_T$.
   • For t = T-1, T-2, …, 0:
     • $G\leftarrow \gamma G+R_{t+1}$
     • If $s$ is the first time in the episode:
       • Append $G$ to $\text{returns}(s)$.
       • $V(s)\leftarrow \text{average}(\text{returns}(s))$.

The reason why we call it ‘first-visit’ is that we only update the value function for the first time we visit a state in an episode. Thus we can avoid the bias caused by multiple visits to the same state in an episode. However, this method may have high variance because it only uses one return for each state in an episode.

Incremental Monte Carlo method

The first-visit Monte Carlo method takes a lot of memory to store the returns for each state, which is not efficient. The incremental Monte Carlo method uses an incremental update rule to estimate the value function without storing all the returns. The algorithm is as follows:

1. Initialization:
   • For any $s\in S$,$V(s)\in \mathbb{R}$, $N(s)=0$, $G=0$.
2. Loop for each episode:
   • Generate an episode following policy $\pi$: $S_0,A_0,R_1,S_1,A_1,R_2,\cdots ,S_T$.
   • For t = T-1, T-2, …, 0:
     • $G\leftarrow \gamma G+R_{t+1}$
     • If $s$ is the first time in the episode:
       • $N(s)\leftarrow N(s)+1$
       • $V(s)\leftarrow V(s)+\frac{1}{N(s)}(G-V(s))$.

Interesting, online softmax also takes the same update rule as the incremental Monte Carlo method. Great job.

Besides, incremental MC provides more design space for us to tackle some problems in practice. For example, we can use a constant step size $\alpha$ instead of $\frac{1}{N(s)}$ to update the value function, which is called constant step size MC method. It is useful when the environment is non-stationary, which means the reward function and transition probability may change over time. In this case, we want to give more weight to recent returns than old returns, which can be achieved by using a constant step size $\alpha$:$$V(s)\leftarrow V(s)+\alpha (G-V(s))$$

Some properties of Monte Carlo methods

1. Monte Carlo methods are model-free, which means they do not require the knowledge of the environment’s dynamics (transition probabilities and reward function).
2. Monte Carlo methods take the simpliest approach to estimate the value function, which is to average the returns following the policy. However, this method may have high variance because it only uses one return for each state in an episode.
3. One key to note is that Monte Carlo methods can only be applied to finite MDPs, which means the state space and action space must be finite.

Importance sampling

Let’s try to estimate a custom distribution $p(x)$ ‘s expectation.$$\begin{array}{rl}{E}_{x\sim p}[f(x)]& =\int f(x)p(x)dx\\ & =\int f(x)\frac{p(x)}{q(x)}q(x)dx\\ & =E_{x\sim q}\left[f(x)\frac{p(x)}{q(x)}\right]\end{array}$$
Then we reassign the importance sampling weight $w(x)=\frac{p(x)}{q(x)}$, we can rewrite the above equation as:$$E_{x\sim p}[f(x)]=E_{x\sim q}\left[f(x)w(x)\right]$$

Off-policy Monte Carlo methods via Importance Sampling

We can use the cumulative reward function of policy $\mu$ to justify policy $\pi$, and then weight the cumulative reward function by the importance ratio between $\pi$ and $\mu$ to estimate the value function of policy $\pi$. The algorithm is as follows:

Every episode would be mutified by the importance sampling ratio:$$G_t^{\pi /\mu }=\frac{\pi (A_t|S_t)}{\mu (A_t|S_t)}\frac{\pi (A_{t+1}|S_{t+1})}{\mu (A_{t+1}|S_{t+1})}\cdots \frac{\pi (A_{T-1}|S_{T-1})}{\mu (A_{T-1}|S_{T-1})}{G}_t$$

So we then update the value function by:$$V(s)\leftarrow V(s)+\frac{1}{N(s)}(G_t^{\pi /\mu }-V(s))$$

Sample by importance sampling will significantly increase the variance of the return, which is because the importance sampling ratio can be very large when $\pi$ and $\mu$ are very different.

Temporal-Difference Learning

Temporal-Difference (TD) is a method combining the MC method and DP method, which name comes from the fact that it uses the diff of estimated value function at two consecutive time steps to update the value function. There are two key ideas in TD learning: TD error and TD target.

For state value funtion $V$, after a transition from state $s$ to state $s’$ with reward $r$, the TD error is defined as:$$\delta =r+\gamma V(s’)-V(s)$$
The TD target is defined as:$$\hat{V}=r+\gamma V(s’)$$

As for the TD in Bellman expectation equation, the TD error is used in estimating the expect part.

Some details of TD learning

The simpliest TD learning algorithm is called TD(0), which updates the value function by the TD error at each time step. The key equation of TD(0) is as follows:$$V(s)\leftarrow V(s)+\alpha \delta =V(s)+\alpha (r+\gamma V(s’)-V(s))$$

Why we update like this?
The Bellman expectation equation is rewritten as:

$$E_{\pi }\left[R_{t+1}+\gamma V^{\pi }(S_{t+1})-V^{\pi }(S_t)|S_t=s\right]=0$$
That’s all. We want to make the TD error as small as possible, which means we want to make the estimated value function as close as possible to the true value function. Thus, we can use the TD error to update the value function.

The TD method introduce the bootstrapping idea, which means we use the estimated value function to update the value function. This is different from the MC method, which uses the actual return to update the value function. The bootstrapping idea can significantly reduce the variance of the return, but it may introduce bias because we are using an estimated value function to update the value function.

Contrast between TD and MC methods

They have the same goal: Learn the value function from episodes of experience. However, they have different approaches to achieve this goal. The MC method uses the actual return to update the value function, which can have high variance but no bias. The TD method uses the estimated value function to update the value function, which can have low variance but may introduce bias.

TD method	MC method
update value function $V(s)$ like $V(s)\leftarrow V(s)+\alpha (r+\gamma V(s’)-V(s))$	update value function $V(s)$ like $V(s)\leftarrow V(s)+\frac{1}{N(s)}(G_t-V(s))$

The object of TD is $R_t+\gamma V(s_{t+1})$, which is called TD target, while the object of MC is $G_t$, which is the actual return. The TD method’s error is called TD error, which is defined as $\delta =r+\gamma V(s’)-V(s)$, while the MC method’s error is defined as $G_t-V(s)$.

The strengths and limitations of TD learning and MC learning

TD method can learn until the end of an episode:

• After each step in an episode, TD method can update the value function use the former value function, which means it can learn until the end of an episode. However, MC method can only update the value function after the end of an episode, which means it cannot learn until the end of an episode.
• TD method can learn from incomplete episodes, which means it can learn from episodes that are not terminated. However, MC method can only learn from complete episodes, which means it cannot learn from episodes that are not terminated.

Tradeoff between bias and variance

	Estimator	Bias	Variance
MC	$G_t$	Unbiased: $E[G_t]=V^{\pi }(s)$	Higher
TD (real)	$R_{t+1}+\gamma V^{\pi }(S_{t+1})$	Unbiased: $E[R_{t+1}+\gamma V^{\pi }(S_{t+1})]=V^{\pi }(s)$	Lower
TD (actual)	$R_{t+1}+\gamma V(S_{t+1})$	Biased: $E[R_{t+1}+\gamma V(S_{t+1})]$ ≠ $V^{\pi }(s)$	Lower

Note: The real TD target uses the true $V^{\pi }$, which is unknown in practice. The actual TD target uses the current estimate $V$, introducing bias. Despite the bias, TD typically has lower variance than MC because it bootstraps from a single step rather than a full trajectory.

Multi-step TD learning

The TD(0) method only uses the immediate reward and the estimated value of the next state to update the value function, which may not be sufficient to capture the long-term dependencies in the environment. The multi-step TD learning method uses the rewards and estimated values of multiple future states to update the value function, which can better capture the long-term dependencies in the environment. We will introduce it by leading into n-step cumulate reward function and n-step TD target.

N-step cumulate reward function

Consider the following n-step cumulate reward function:$$G_t^{(n)}=R_t+\gamma R_{t+1}+\cdots +{\gamma }^{n-1}{R}_{t+n-1}+{\gamma }^{n}V(S_{t+n})$$
It seems make sense to use the n-step cumulate reward function to update the value function, which is called n-step TD learning. The key equation of n-step TD learning is as follows:$$V(s)\leftarrow V(s)+\alpha (G_t^{(n)}-V(s))$$

N-step mean cumulate reward function

Can we take up the information of different n-step cumulate reward function to update the value function? The answer is yes.
We can use a weighted average of different n-step cumulate reward functions to update the value function, which is called n-step mean TD learning. The key weight figure of weighted average is as follows:

So the n-step mean cumulate reward function is defined as:$$G_t^{\lambda }=(1-\lambda )\sum _{n=1}^{\infty }{\lambda }^{n-1}{G}_t^{(n)}$$
Then we can update the value function by:$$V(s)\leftarrow V(s)+\alpha (G_t^{\lambda }-V(s))$$

This is called TD($\lambda$) method, which is a generalization of TD(0) and MC methods. When $\lambda =0$, TD($\lambda$) reduces to TD(0) method, and when $\lambda =1$, TD($\lambda$) reduces to MC method. Thus, by adjusting the value of $\lambda$, we can control the bias-variance tradeoff in the estimation of the value function.

Conclusion about TD(λ) method

• Unless the $lambda$ is 0, TD($\lambda$) mothod is unbiased, because it’s a weighted average of unbiased n-step TD targets.

• The variance of TD($\lambda$) method is lower than that of MC method, because it uses bootstrapping to update the value function, which can reduce the variance of the return. However, the variance of TD($\lambda$) method is higher than that of TD(0) method, because it uses more rewards and estimated values to update the value function, which can increase the variance of the return.

  $$\text{Var}(aX+bY)=a^2\text{Var}(X)+b^2\text{Var}(Y)$$

• Empirically $\lambda$ is not quite commom because fast credit assignment for a given action is preferred. So MC or TD(0) is more commonly used in practice. However, TD($\lambda$) method can be useful when we want to balance the bias-variance tradeoff in the estimation of the value function, which can be achieved by adjusting the value of $\lambda$.

So TD($\lambda$) use $\lambda$ as variable while n-step TD use $n$ as variable. TD($\lambda$) is a generalization of n-step TD, which can be seen as a weighted average of infin-step TD targets. By adjusting the value of $\lambda$, we can control the bias-variance tradeoff in the estimation of the value function, which can be useful in practice when we want to balance the bias and variance in the estimation of the value function.

Conclusion

In this post, we have introduced the model-free Reinforcement learning, which does not require the simulation of the environment and the construction of MDPs. We have introduced two methods to estimate the value function from episodes of experience: Monte Carlo methods and Temporal-Difference learning. We have also introduced the n-step TD learning method, which uses the rewards and estimated values of multiple future states to update the value function, which can better capture the long-term dependencies in the environment. Finally, we have discussed the bias-variance tradeoff in the estimation of the value function, which can be controlled by adjusting the value of $\lambda$ in TD($\lambda$) method.

Introduction

In the previous post, we have introduced the Bellman equation and the linear programming formulation for MDP. In this post, we will discuss the model-based Reinforcement learning, which is a method to solve the MDP when we do not have the model of the environment.

The Settings of RL

Typically, RL is framed as MDP, exploring the enviroment and learning the optimal policy.
Generally, we can only observe the episodes and usually, we do not have the model of the environment.

So we need to introduce the model into our RL project. Model-based RL actually is a method to solve the MDP.

Dynamic Programming Based RL

Dynamic Programming for finite MDP

Our objective function is simple, just the expected return, which is defined as:$$\underset{\pi }{\max }{E}_{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}|s_0=s\right]$$

In the first episode of the series, we introduced Backward induction, which we can start from the last step and then recursively solve the problem. However, this method is not efficient for large state space, and it requires the state transition.

But meanwhile, we can also use the Bellman equation of value function to tackle the problem:$$V^{\pi }(s)=\sum _{a\in A}\pi (a|s)\left[\underset{\text{immediate reward}}{\underbrace{R(s,a)}}+\underset{\text{discount}}{\underbrace{\gamma }}\sum _{s’\in S}\underset{\text{transition}}{\underbrace{P(s’|s,a)}}\underset{\text{future value}}{\underbrace{V^{\pi }(s’)}}\right]$$

Optimal Value Function

For a state $s$, we can define the optimal value function as the maximum value function over all policies:$$V^{\ast }(s)=\underset{\pi }{\max }{V}^{\pi }(s)$$
So the optimal value function is as follows:$$V^{\ast }(s)=\underset{a\in A}{\max }R(s,a)+\gamma \sum _{s’\in S}P(s’|s,a)V^{\ast }(s’)$$

So the best policy can be derived from the optimal value function as:$${\pi }^{\ast }(a|s)=\arg \underset{a\in A}{\max }R(s,a)+\gamma \sum _{s’\in S}P(s’|s,a)V^{\ast }(s’)$$

for any state $s$ and policy $\pi$, there is:$$V^{\ast }(s)=V^{{\pi }^{\ast }}(s)\ge V^{\pi }(s)$$

Obviously, the value function relates to the policy, so we can iterate the optimal value function and the optimal policy until convergence. They are called Value Iteration and Policy Iteration respectively.

Value Iteration

For an MDP which is finite in both state and action space, we can use the value iteration to solve the problem. The value iteration is as follows:

1. Initialize $V(s)=0$ for all $s\in S$
2. For each state $s\in S$, update the value function as:
   $V(s)\leftarrow {\max }_{a\in A}R(s,a)+\gamma {\sum }_{s’\in S}P(s’|s,a)V(s’)$
3. Repeat step 2 until convergence.

NOTE: There isn’t any specific order to update the value function, we can update the value function in any order. But the convergence rate may be different.

Sync & Async Value Iteration

Sync value iteration need to store two copies of value funtion:

1. For any state $s$, we update the value function as:
   $V_{new}(s)\leftarrow {\max }_{a\in A}R(s,a)+\gamma {\sum }_{s’\in S}P(s’|s,a)V_{old}(s’)$
2. After updating all states, we copy the new value function to the old value function:
   $V_{old}\leftarrow V_{new}$

Async value iteration only need to store one copy of value function:
$V(s)\leftarrow {\max }_{a\in A}R(s,a)+\gamma {\sum }_{s’\in S}P(s’|s,a)V(s’)$

Policy Iteration

The assumption of MDP is the same as the value iteration, which is finite in both state and action space. The policy iteration is as follows:

1. Randomly initialize a policy $\pi$ and a value function $V(s)=0$ for all $s\in S$
2. Repeat the following steps until convergence:
3. Policy Evaluation: For each state $s\in S$, update the value function as:
   $V(s)\leftarrow {\sum }_{a\in A}\pi (a|s)\left[R(s,a)+\gamma {\sum }_{s’\in S}P(s’|s,a)V(s’)\right]$
4. Policy Improvement: For each state $s\in S$, update the policy as:
   $\pi (a|s)\leftarrow \arg {\max }_{a\in A}R(s,a)+\gamma {\sum }_{s’\in S}P(s’|s,a)V(s’)$

Obviously, the Policy Iteration will be more expensive than the Value Iteration, since it needs to evaluate the policy in each iteration. However, the Policy Iteration can converge faster than the Value Iteration, since it can update the policy in each iteration.

Let’s contrast the two methods:

Method	Value Iteration	Policy Iteration
Update	Value function	Policy and value function
uses	Bellman optimality equation	Bellman expectation equation

NOTE:

1. Value iteration is a greedy method, we always use the best.
2. Update the value function by Bellman equation in Policy Iteration is expensive.
3. For smaller space MDP, Policy Iteration is faster than Value Iteration, but for larger space MDP, Value Iteration is faster than Policy Iteration.
4. If there isn’t any state transition circle, the value iteration is better.

Bellman operators

In fact, we have introduced the Bellman operators in the previous post, but we haven’t discussed it in detail.

Why Policy Iteration and Value Iteration can converge to the optimal value function? The key is that Bellman operators are contraction mappings.

Bellman operator is the collection of below functions:

1. Bellman expectation operator, usually denoted as ${\mathcal{T}}^{\pi }$, which is defined as:

   $${\mathcal{T}}^{\pi }V(s)=\sum _{a\in A}\pi (a|s)\left[R(s,a)+\gamma \sum _{s’\in S}P(s’|s,a)V(s’)\right]$$

2. Bellman optimality operator, usually denoted as ${\mathcal{T}}^{\ast }$ or $\mathcal{T}$, which is defined as:

   $$\mathcal{T}V(s)=\underset{a\in A}{\max }R(s,a)+\gamma \sum _{s’\in S}P(s’|s,a)V(s’)$$

They can be used on the state value function and action value function:

• expectation operator is used in the policy iteration, used for computing
  the value function of a given policy, while is the inner loop of the policy iteration.
• optimality operator is used in the value iteration, used for computing the optimal value function, while is the main loop of the value iteration.

Both the Bellman expectation operator and the Bellman optimality operator can be defined on the action value function and the state value function:

1. Bellman expectation operator on V-function:

$$\begin{array}{rl}{V}^{\pi }(s)& =E_{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_t\mid s_0=s\right]\\ & =E_{\pi }\left[R(s_0,a_0)+\gamma \sum _{s’\in S}P(s’|s,a)\pi (a|s)V^{\pi }(s’)\right]\\ & =\sum _{a\in A}\pi (a|s)\left[R(s,a)+\gamma \sum _{s’\in S}P(s’|s,a)V^{\pi }(s’)\right]\\ & =({\mathcal{T}}^{\pi }{V}^{\pi })(s)\end{array}$$

2. Bellman optimality operator on V-function:

$$\begin{array}{rl}{V}^{\ast }(s)& =\underset{\pi }{\max }{E}_{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_t\mid s_0=s\right]\\ & =\underset{a\in A}{\max }R(s,a)+\gamma \sum _{s’\in S}P(s’|s,a)V^{\ast }(s’)\\ & =(\mathcal{T}{V}^{\ast })(s)\end{array}$$

3. Bellman expectation operator on Q-function:

$$\begin{array}{rl}{Q}^{\pi }(s,a)& =E_{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_t\mid s_0=s,a_0=a\right]\\ & =E_{\pi }\left[R(s_0,a_0)+\gamma \sum _{s’\in S}P(s’|s,a)\pi (a|s)Q^{\pi }(s’,a’)\right]\\ & =R(s,a)+\gamma \sum _{s’\in S}P(s’|s,a)\sum _{a’\in A}\pi (a’|s’)Q^{\pi }(s’,a’)\\ & =({\mathcal{T}}^{\pi }{Q}^{\pi })(s,a)\end{array}$$

4. Bellman optimality operator on Q-function:

$$\begin{array}{rl}{Q}^{\ast }(s,a)& =\underset{\pi }{\max }{E}_{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_t\mid s_0=s,a_0=a\right]\\ & =R(s,a)+\gamma \sum _{s’\in S}P(s’|s,a)\underset{a’\in A}{\max }{Q}^{\ast }(s’,a’)\\ & =(\mathcal{T}{Q}^{\ast })(s,a)\end{array}$$

Due to the contraction property of the Bellman operators, we can guarantee the convergence of the value iteration and policy iteration to the optimal value function.

Model RL

In the above sections, our objective environment is a known MDP, all our methods are based on the assumption that we have the model of the environment, which is the transition probability and the reward function. However, in many real-world scenarios, we do not have the model of the environment, so we need to learn the model from the data.

There are two basic thoughts to learn the model of the environment:

1. learn the state transition probability$P(s’|s,a)$:

   $$P(s’|s,a)=\frac{N(s,a,s’)}{N(s,a)}$$

   where $N(s,a,s’)$ is the number of times we have observed the transition from state $s$ to state $s’$ when taking action $a$, and $N(s,a)$ is the number of times we have observed taking action $a$ in state $s$.

2. learn the reward function $R(s,a)$:

   $$R(s,a)=\text{average}\left(R_t|s_t=s,a_t=a\right)$$

   where $N(s,a)$ is the number of times we have observed taking action $a$ in state $s$, and $R(s,a)$ is the average reward we have observed when taking action $a$ in state $s$.

The simple simulate algorithm is as follows:

1. randomly initialize a policy $\pi$
2. repeat the following steps until convergence:
3. collect data by executing the policy $\pi$ in the environment, and store the transition data in a replay buffer.
4. learn the model of the environment from the replay buffer, which includes learning the state transition probability and the reward function.
5. solve the MDP with the learned model to get the optimal policy ${\pi }^{\ast }$.

Other method to solve this is not learning the MDP, instead we learn the value function directly from the data, which is called model-free RL, we will discuss it in the next post.

Conclusion

In this post, we have introduced the model-based Reinforcement learning, which is a method to solve the MDP when we do not have the model of the environment. We have discussed the value iteration and policy iteration, which are two basic methods to solve the MDP. We have also introduced the Bellman operators, which are the key to guarantee the convergence of the value iteration and policy iteration. Finally, we have introduced the simple simulate algorithm, which is a method to learn the model of the environment and solve the MDP with the learned model. In the next post, we will discuss the model-free Reinforcement learning, which is a method to learn the value function directly from the data without learning the model of the environment.

Introduction

Given the former post where we have introduced the MDP and some basic properties, we are now ready to discuss the MDP-based Reinforcement learning. But first, we need to introduce the solution of MDP.

Bellman Equation

If we have learned the previous post, we will know that there are two types of value function, state value function and action value function. Their mathematical definitions are as follows:$$V^{\pi }(s)=E_{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}|s_0=s\right]$$

Instinctively, the state value function is the expected return when we start from state $s$ and follow policy $\pi$. Similarly, the action value function is defined as:

$$Q^{\pi }(s,a)=E_{\pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}|s_0=s,a_0=a\right]$$

Here, it represents the expected return when we start from state $s$, take action $a$, and then follow policy $\pi$ thereafter.

On the other hand, we have a accumulate reward function, which is defined as:$$G_t=R_t+\gamma R_{t+1}+{\gamma }^2{R}_{t+2}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k}$$
It can be recursively defined as:$$G_t=R_t+\gamma G_{t+1}$$

So, we can rewrite the state value function as:$$V^{\pi }(s)=\sum _a\pi (a|s)\left[R(s,a)+\gamma \sum _{s’}P(s’|s,a)V^{\pi }(s’)\right]$$
Above is the Bellman expectation equation for the state value function. Now, our question is to choose the best policy $\pi$ to maximize the value function. We can define the optimal state value function as:$$V^{\ast }(s)=\underset{\pi }{\max }{V}^{\pi }(s)$$

Due to the Principle of Optimality: Each stage of an optimal policy must be optimal for the remaining stages, we can derive the Bellman optimality equation for the state value function as:$$V^{\ast }(s)=\underset{a}{\max }\left[R(s,a)+\gamma \sum _{s’}P(s’|s,a)V^{\ast }(s’)\right]$$

Above is the Bellman optimality equation for the state value function.

Linear Programming for MDP

We have a key observation that the Bellman optimality equation can be rewritten as a linear programming problem. The linear programming formulation for MDP is as follows:

$$\begin{array}{rl}\text{minimize}& \sum _{s}V(s)\\ \text{subject to}& V(s)\ge R(s,a)+\gamma \sum _{s’}P(s’|s,a)V(s’),\\ & \forall s\in S,a\in A\end{array}$$

Proof:
The first part is to show that the optimal value function $V^{\ast }$ is a feasible solution to the above linear programming problem. We can see that for any state $s$ and action $a$, we have:$$\begin{gathered} V^{\ast }(s)=\underset{a’}{\max }\left[R(s,a’)+\gamma \sum _{s’}P(s’|s,a’)V^{\ast }(s’)\right] \\ \ge R(s,a)+\gamma \sum _{s’}P(s’|s,a)V^{\ast }(s’) \end{gathered}$$
Thus, $V^{\ast }$ satisfies the constraints of the linear programming problem.
The second part is to show that any feasible solution satisfying the constraints must be greater than or equal to $V^{\ast }$.
Given that the optimal policy ${\pi }^{\ast }$ choose one action ${\pi }^{\ast }(s)$ for each state $s$, LP constraints imply that for any state $s$:$$V(s)\ge R(s,{\pi }^{\ast }(s))+\gamma \sum _{s’}P(s’|s,{\pi }^{\ast }(s))V(s’)$$
Let’s write them in matrix form:$$V\ge R^{{\pi }^{\ast }}+\gamma P^{{\pi }^{\ast }}V$$
while the $R^{{\pi }^{\ast }}$ is the reward vector under policy ${\pi }^{\ast }$, and $P^{{\pi }^{\ast }}$ is the transition matrix under policy ${\pi }^{\ast }$. We can rearrange the above inequality as:$$(I-\gamma P^{{\pi }^{\ast }})V\ge R^{{\pi }^{\ast }}$$
Since $\gamma <1$, we can conclude that $I-\gamma P^{{\pi }^{\ast }}$ is invertible, and we can get its inverse as:$$(I-\gamma P^{{\pi }^{\ast }}{)}^{-1}=\sum _{k=0}^{\infty }(\gamma P^{{\pi }^{\ast }}{)}^k$$
Obviously, the above inverse is a non-negative matrix. Thus, we can multiply both sides of the inequality by $(I-\gamma P^{{\pi }^{\ast }}{)}^{-1}$ to get:$$V\ge (I-\gamma P^{{\pi }^{\ast }}{)}^{-1}{R}^{{\pi }^{\ast }}=V^{{\pi }^{\ast }}$$
Since $V^{\ast }\ge V^{{\pi }^{\ast }}$, we can conclude that $V\ge V^{\ast }$.
So, we have shown that any feasible solution is greater than or equal to $V^{\ast }$, and the optimal value function $V^{\ast }$ is a feasible solution. Thus, the optimal solution to the linear programming problem is $V^{\ast }$.

Given we have the $V^{\ast }$, we can easily derive the optimal policy ${\pi }^{\ast }$ as:$${\pi }^{\ast }(s)=\arg \underset{a}{\max }\left[R(s,a)+\gamma \sum _{s’}P(s’|s,a)V^{\ast }(s’)\right]$$

Here I asked claude to give me a simple explanation of the equivalence between this greedy like policy decision and the optimal policy. The formal proof may be need to use the fixed point theorem, but it is beyond the scope of this post. We just need to remember that the optimal policy can be derived from the optimal value function by choosing the action that maximizes the expected return.

The Dual Linear Programming for MDP

The dual linear programming formulation for MDP is as follows:$$\begin{array}{rl}\text{maximize}& \sum _{s,a}\rho (s,a)R(s,a)\\ \text{subject to}& \sum _a\rho (s’,a)=\sum _{s,a}\rho (s,a)P(s’|s,a),\\ & \forall s’\in S\\ & \rho (s,a)\ge 0,\forall s\in S,a\in A\end{array}$$

If the initial state distribution $\mu (s)>0$ for all $s\in S$, then let
$w(s)=\mu (s)$, the target function means the expected accumulated reward represented by the occupancy measure, and the constraints means the flow conservation constraints.

Assume that the optimal solution is ${\rho }^{\ast }(s,a)$, we can derive the optimal policy from Theorem 2 as:$${\pi }^{\ast }(s)=\frac{{\rho }^{\ast }(s,a)}{{\sum }_a{\rho }^{\ast }(s,a)}$$

Comparison between the Primal and Dual Linear Programming for MDP

Dimension	Primal LP	Dual LP
variable	state value function $V(s)$	occupancy measure $\rho (s,a)$
objective	minimize ${\sum }_{s}V(s)$	maximize ${\sum }_{s,a}\rho (s,a)R(s,a)$
constraints	Bellman optimality constraints	flow conservation constraints
explanation	state value	action frequency

Summary

At the beginning of this post, I tried to introduce the MDP-based Reinforcement learning, but I found that the solution of MDP takes a lot of space, so I just introduce the Bellman equation and the linear programming formulation for MDP. In the next post, I will introduce the value iteration and policy iteration algorithms for solving MDP, which are based on the Bellman equation.

The category of decision making problem

dimension	single step	multi step
one person	optimization problem	RL, to the best situation
multi person	static game	dynamic game, MARL.etc

Dynamic programming

Dynamic program is used to solve the Sequential decision making problem, feature of this problem is that it’s decision making process is sequential, and the decision at one step will affect the next step, and the reward is received at the end of decision making process, not at each step.

For an example, given a maze like problem below, the agent need to find a way from Position A to Position B, and the time of each way is different. Agent need to find the way with the least time. A simple way to solve this is to list all the possible paths, but if there is a circle, if the map is large, this will be unfeasible.

A better way to solve this is Backward induction, we start from the end point, and for evey point we calculate the time to reach the end point, then we regart the selected point as the new end point, and repeat this process until we reach the start point. This is a dynamic programming method, and it can solve the problem in polynomial time. But due to we need find a backward path, this method is only suitable for DAG, if there is a circle, this method will fail.

The example is just a introduction, we can summarize the features of dynamic programming as follows:

• it start from the end, and caculate the best action for each state.
• it traverse all the states, and for each state, it calculate the best action, and the value of this state.
• it need to define the state, path(state transition), time(online reward)

So it lead to the Principle of Optimality:

An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

Markov Decision Process

Stochastic Process

A stochastic process is a collection of random variables, which can be used to describe the evolution of a system over time. It’s mathematical definition is as follows:$$P(X_{t+1}|X_t,X_{t-1},\dots ,X_0)$$
This means that the probability of the next state $X_{t+1}$ depends on the current state $X_t$ and all the previous states $X_{t-1},\dots ,X_0$.

Markov Process

Compared to stochastic process, Markov process has a stronger assumption, which is “the future is independent of the past given the present”. Mathematically, it’s definition is as follows:$$P(X_{t+1}|X_t,X_{t-1},\dots ,X_0)=P(X_{t+1}|X_t)$$
This means that the probability of the next state $X_{t+1}$ only depends on the current state $X_t$, and is independent of all the previous states $X_{t-1},\dots ,X_0$.

Trying to understand it’s property is that the current state contains all the information about the past, so we can make decision based on the current state without worrying about the past.

Markov Decision Process

Markov Decision Process (MDP) provides a mathematical framework for modeling decision making in situations where the outcome is partly random, partly under the control of a decision maker. An MDP is defined by the following components:

• State space (S): A set of all possible states in the environment.
• Action space (A): A set of all possible actions that the agent can take
• Transition function (P): A function that defines the probability of transitioning from one state to another given a specific action. It is denoted as $P(s’|s,a)$, which represents the probability of transitioning to state $s’$ from state $s$ after taking action $a$.
• Reward function (R): A function that defines the reward received after transitioning from one state to another given a specific action. It is denoted as $R(s,a)$, which represents the reward received after taking action $a$ in state $s$. Sometimes only relates to the State.
• Discount factor (γ): A factor that determines the importance of future rewards. It is a value between 0 and 1, where a value closer to 0 makes the agent prioritize immediate rewards, while a value closer to 1 makes the agent consider future rewards more heavily.

The dynamic feature of MDP

The whole process of MDP is dynamic as follows:

1. The agent observes the current state $s_t$.
2. The agent selects an action $a_t$ based on its policy $\pi (a|s)$, which is a mapping from states to actions.
3. The agent gets a reward $R(s_t,a_t)$.
4. The MDP transitions to a new state $s_{t+1}$ according to the transition function $P(s_{t+1}|s_t,a_t)$.

The total reward that the agent receives over time is often defined as the discounted sum of rewards:$$G_t=R(s_t,a_t)+\gamma R(s_{t+1},a_{t+1})+{\gamma }^{2}R(s_{t+2},a_{t+2})+\dots =\sum _{k=0}^{\infty }{\gamma }^{k}R(s_{t+k},a_{t+k})$$

Markov Policy

In the context of MDP, a policy is a function that depends on the history:$$h_t=(s_0,a_0,s_1,a_1,\dots ,s_{t-1},a_{t-1},s_t)\pi (a_t|h_t)=P(a_t|h_t)$$

But a Markov policy is a special type of policy that only depends on the current state:$$\pi (a_t|s_t)=P(a_t|s_t)$$

---

In the RL setting, we usually assume that the policy is a Markov policy. Why?

The MDP has Markov property, which means the future is independent of the past given the present, so there is no special information in the history that can help us make better decision, so we can just use the current state to make decision.More informally, for any policy relying on the history, we can find a Markov policy that at least performs as well as it does, so we can just focus on Markov policy without loss of generality.proof(the 26th and 27th slides of the lecture)

---

The category of MDP Policy

At the time demension, we can categorize the policy into two types:

• Stationary policy: A policy that does not change over time. It is defined as $\pi (a|s)$, which means the action taken in state $s$ is the same at any time step.
• Non-stationary policy: A policy that can change over time. It is defined as ${\pi }_t(a|s)$, which means the action taken in state $s$ can be different at different time steps.

At the probability distribution demension, we can categorize the policy into two types:

• Deterministic policy: A policy that always selects the same action for a given state. It is defined as $\pi (s)=a$, which means the action taken in state $s$ is always $a$.
• Stochastic policy: A policy that selects actions according to a probability distribution. It is defined as $\pi (a|s)=P(a|s)$, which means the action taken in state $s$ is selected according to the probability

---

In the RL setting, we usually assume that the policy is a stationary policy. Why?
Typically, we consider the infinite horizon setting. There is also a proof that for any non-stationary policy, we can find a stationary policy that at least performs as well as it does, so we can just focus on stationary policy without loss of generality. proof(the 29th and 32th slides of the lecture)

---

The best policy for MDP

There is a theorem:

In a situation that the discount factor $\gamma <1$, while the state and action space are finite and the horizon is infinite, there exists a deterministic
and stationary policy ${\pi }^{\ast }$ that is optimal, which means for any policy $\pi$, we have $V^{{\pi }^{\ast }}(s)\ge V^{\pi }(s)$.

Proof: Puterman, Martin L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.

The goal of MDP

Our goal is to choose the action to maximize the expected reward, which is defined as follows:$$\text{E}[R(s_0,a_0)+\gamma R(s_1,a_1)+{\gamma }^{2}R(s_2,a_2)+\dots ]=\text{E}[\sum _{t=0}^{\infty }{\gamma }^{t}R(s_t,a_t)]$$

So we can define the value function for a policy $\pi$ as follows:$$V^{\pi }(s)=\text{E}[\sum _{t=0}^{\infty }{\gamma }^{t}R(s_t,a_t)|s_0=s]$$
This means the expected reward that the agent can get starting from state $s$ and following policy $\pi$.

Occupancy Measure

In MDP context, the occupancy measure is a way to represent the discounted state-action expectation under a policy $\pi$, also known as state-action visitation distribution. It is defined as follows:$${\rho }^{\pi }(s,a)=\underset{a\sim \pi (s),,s’\sim p(s,a)}{\mathbb{E}}\left[\sum _{t=0}^{\infty }{\gamma }^t\mathbb{I}(s_t=s,a_t=a)\right]$$

while the $s\sim p(s,a)$ means the state transition, which is defined as follows:$$s_{t+1}\sim p(s_t,a_t)$$

On the other hand, the state occupancy measure is defined as follows:$${\rho }^{\pi }(s)=\underset{a\sim \pi (s),,s’\sim p(s,a)}{\mathbb{E}}\left[\sum _{t=0}^{\infty }{\gamma }^t\mathbb{I}(s_t=s)\right]$$

How to compute the occupancy measure?

State occupancy measure

We assume that the initial state distribution is $\mu (s)$, then we can compute the state occupancy measure as follows:$${\rho }^{\pi }(s’)=\mu (s’)+\gamma \sum _s{p}^{\pi }(s’|s){\rho }^{\pi }(s)$$

then we can solve the fomula:$${\rho }^{\pi }={\left(I-\gamma (P_{SS’}^{\pi }{)}^T\right)}^{-1}\mu$$

State-action occupancy measure

We can compute the state-action occupancy measure as follows:$${\rho }^{\pi }(s,a)=\mu (s’)\pi (a’|s’)+\gamma \sum _s{p}^{\pi }(s’|s){\rho }^{\pi }(s,a)$$

Pay attention that the whole process is flow conservation. Because the state-action occupancy measure is the expected discounted number of times that the agent takes action $a$ in state $s$, so the total flow into state $s$ must equal the total flow out of state $s$. This is why we have the flow conservation constraint in the computation of occupancy measure.

Some Properties of Occupancy Measure

Obviously, from the definition of the measures:

• ${\rho }^{\pi }(s)={\sum }_a{\rho }^{\pi }(s,a)$
• ${\rho }^{\pi }(s,a)=\pi (a|s){\rho }^{\pi }(s)$

We have two important theorems about the occupancy measure:

• Theorem 1: For two policies $\pi$ and $\pi ’$ interacting with the same dynamic environment, if ${\rho }^{\pi }={\rho }^{\pi ’}$, then ${\pi }_1={\pi }_2$.
• Theorem 2: Given a Occupancy measure $\rho$, the only policy that can generate this occupancy measure is ${\pi }_{\rho }(s,a)=\frac{\rho (s,a)}{{\sum }_a\rho (s,a)}$.

Accumulated reward for a policy

As we have defined the occupancy measure, we can compute the accumulated reward for a policy $\pi$ as follows:$$\begin{array}{rl}\mathbb{V}(\pi )& =\underset{a\sim \pi (\cdot |s),s’\sim p(\cdot |s,a)}{\mathbb{E}}\left[R(s_0,a_0)+\gamma R(s_1,a_1)+{\gamma }^{2}R(s_2,a_2)+\dots \right]\\ & =\sum _{s,a}\underset{a\sim \pi (\cdot |s),,s’\sim p(\cdot |s,a)}{\mathbb{E}}\left[R(s,a)\right]{\rho }^{\pi }(s,a)\\ & =\sum _{s,a}R(s,a){\rho }^{\pi }(s,a)\\ & =\underset{{\rho }^{\pi }}{\mathbb{E}}\left[R(s,a)\right]\end{array}$$

Value function and Q function

The value function is used to evaluate a state or a state-action pair, given a policy $\pi$.

The state value function is usually know as value function, which is defined as follows:$$V^{\pi }(s)=\underset{a\sim \pi (\cdot |s),s’\sim p(\cdot |s,a)}{\mathbb{E}}\left[R(s,a)+\gamma V^{\pi }(s’)\right]$$

The state-action value function is usually know as Q function, which is defined as follows:$$Q^{\pi }(s,a)=\underset{a’\sim \pi (\cdot |s’),,s’’\sim p(\cdot |s’,a’)}{\mathbb{E}}\left[R(s,a)+\gamma Q^{\pi }(s’,a’)\right]$$

---

Obviously, we have the relationship between the value function and the Q function:$$V^{\pi }(s)=\sum _a\pi (a|s)Q^{\pi }(s,a)$$
And we can also compute the value function and Q function using the occupancy measure as follows:$$\begin{array}{rl}{V}^{\pi }(s)& =\sum _{a}R(s,a){\rho }^{\pi }(s,a)\\ Q^{\pi }(s,a)& =R(s,a)+\gamma \sum _{s’}p(s’|s,a)V^{\pi }(s’)\end{array}$$

---

Summary

• MDP provides us a simple but powerful mathematical framework to model the sequential decision making problem.

• The five-tuple of MDP is defined as $(S,A,P,R,\gamma )$, which represents the state space, action space, transition function, reward function and discount factor respectively.

• Markov poverty is the key assumption of MDP, which means the future is independent of the past given the present.

• Policy is the function to choose the action, usually is a conditional probability distribution over actions given states, and we usually assume that the policy is a stationary policy.

• Occupancy measure is a way to represent the discounted state-action expectation under a policy, which can be used to compute the accumulated reward for a policy.

• State value function and state-action value function are used to evaluate a state or a state-action pair, given a policy, and they can be computed using the occupancy measure.