RL 02: Markov Decision Process

• MDP:
  • Environment is fully observable - the current state completely characterizes the process
• Review the Markov Property
  • State captures all the relevant information from the history
• State Transition Matrix
  • Probability of transition from any state to any other state $$P_{s{s}^{\prime }}=P[S_{t+1}=s^{\prime }\mid S_t=s]$$
  • Each row sums to 1 since it covers all possible state transitions

Markov Process

A Markov Process (or Markov Chain) is a tuple $⟨\mathcal{S},\mathcal{P}⟩$

• $\mathcal{S}$ is a (finite) set of states
• $\mathcal{P}$ is a state transition probability matrix,

$${\mathcal{P}}_{s{s}^{\prime }}=\mathbb{P}\left[S_{t+1}=s^{\prime }\mid S_t=s\right]$$

• Markov Reward Process: Markov process with value judgements - now we are also talking about the rewards, not just probabilities of transition.

Markov Reward Process

A Markov Reward Process is a tuple $⟨\mathcal{S},\mathcal{P},\mathcal{R},\gamma ⟩$

• $\mathcal{S}$ is a finite set of states
• $\mathcal{P}$ is a state transition probability matrix,

$${\mathcal{P}}_{s{s}^{\prime }}=\mathbb{P}\left[S_{t+1}=s^{\prime }\mid S_t=s\right]$$

• $\mathcal{R}$ is a reward function, ${\mathcal{R}}_s=\mathbb{E}\left[R_{t+1}\mid S_t=s\right]$
• $\gamma$ is a discount factor, $\gamma \in [0,1]$

• The return (or the goal):
  • Total discounted reward from time step $t$ (rewards are given when you exit a state - hence the first subscript is at $t+1$) $$G_t=R_{t+1}+\gamma R_{t+2}+\dots =\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$
• Why discount:
  • Keeps reward mathematically bounded
  • Humans prefer immediate rewards to far away reward - we do hyperbolic discounting
  • It’s a generalization of markov processes - can set it to 1 if you want and mathematically feasible
• Value function:
  • Expected return of the given state over all possible paths from the state, i.e., $v(s)=E[G_t|S_t=s]$

Bellman equation

Gives us a recursive definition of the value function: The value of current state $v(S_t)$ is the sum of:

• the immediate reward from this state $R_{t+1}$
• discounted value (times $\gamma$) of the successor state, i.e., $\gamma v(S_{t+1})$

$$v(S_t)=E[G_t|S_t=s]=E[R_{t+1}+\gamma v(S_{t+1})|S_t=s]$$

which leads to the recursive Bellman equation:

$$v(s)=R_s+\gamma E[G_{t+1}|S_t=s]$$ $$v(s)=R_s+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}v\left(s^{\prime }\right)$$

which can be expressed more concisely in vector form, with $v$ and $\mathcal{R}$ being column vectors with each entry corresponding to a state.

$$v=\mathcal{R}+\gamma \mathcal{P}v$$

• Bellman equation:

  • Linear equation, can be solved directly (solution being $v=(I-\gamma \mathcal{P}{)}^{-1}\mathcal{R}$), but needs matrix inversion which has complexity $O(n^3)$
  • Solve using
    • DP
    • Monte Carlo evaluation
    • Temporal Difference learning

• Markov Decision Process: Markov reward process + actions

Markov Decision Process

A Markov Decision Process is a tuple $⟨\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ⟩$

• $\mathcal{S}$ is a finite set of states
• $\mathcal{A}$ is a finite set of actions
• $\mathcal{P}$ is a state transition probability matrix,

$${\mathcal{P}}_{s{s}^{\prime }}^a=\mathbb{P}\left[S_{t+1}=s^{\prime }\mid S_t=s,A_t=a\right]$$

• $\mathcal{R}$ is a reward function, ${\mathcal{R}}_s^a=\mathbb{E}\left[R_{t+1}\mid S_t=s,A_t=a\right]$
• $\gamma$ is a discount factor $\gamma \in [0,1]$.

• Note that MDP state transition probabilities now depend on the actions instead of just being stochastic.
• Actions are usually stochastic - agent in a state $s$ can do $a_i$ with the probability $P_i$, which brings us to the notion of a policy:
  • Policy is the distribution of actions over states, or a mapping of states to actions
  • Note that the policy depends on the current state and is independent of the time (in other words, it is stationary).
  • MDP policies are markovian - action only depends on the current state, not history.

A policy is a distribution of actions over states:

$$\pi (a\mid s)=P[A_t=a\mid S_t=s]$$

• Policy determines actions (given the state), which in turn determines the next state and reward.
  • State transition probabilities and expected return is a function of policy now - it’s the transition probability for each action times the probability of taking that action in the current state
  • Specifically, $${\mathcal{P}}_{s,s^{\prime }}^{\pi }=\sum _{a\in \mathcal{A}}\pi (a\mid s){\mathcal{P}}_{s{s}^{\prime }}^a$$ $${\mathcal{R}}_s^{\pi }=\sum _{a\in \mathcal{A}}\pi (a\mid s){\mathcal{R}}_s^a$$
• State value function now depends on the policy.
• We also define a new kind of value function - one over the actions.

Action Value Function

is the expected return starting from state $s$, taking action $a$, and then following policy $\pi$.

$$q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[G_t\mid S_t=s,A_t=a\right]$$

• Action value function helps us determine the best action to take given a state.

Bellman Expectation equation

Just as we did earlier for value function in MRP, we can decompose the state-value and action-value functions for MDP like so:

We can write the action value function as

$$q_{\pi }(s,a)={\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\pi }\left(s^{\prime }\right)$$

and the state value function as

$$v_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)q_{\pi }(s,a)$$

These functions are now recursively defined in terms of each other. Substituting and rewriting them as their own recursive functions, we get:

$$v_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)\left({\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\pi }\left(s^{\prime }\right)\right)$$ $$q_{\pi }(s,a)={\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a\sum _{a^{\prime }\in \mathcal{A}}\pi \left(a^{\prime }\mid s^{\prime }\right)q_{\pi }\left(s^{\prime },a^{\prime }\right)$$

Once again, writing them in vector form using our new definitions of ${\mathcal{R}}^{\pi }$ and ${\mathcal{P}}^{\pi }$ gives:

$$v_{\pi }={\mathcal{R}}^{\pi }+\gamma {\mathcal{P}}^{\pi }{v}_{\pi }$$

which again has a direct solution:

$$v_{\pi }={\left(I-\gamma {\mathcal{P}}^{\pi }\right)}^{-1}{\mathcal{R}}^{\pi }$$

• Basic idea remains that value functions are recursive and you get current reward and then move on to do the same calculation for all the things we might do from there and all the places we might arrive at.
• But does it tell us the best way to behave?
• Optimal policies:
  • The optimal state value function is the maximum value over all policies. It is the maximum possible reward you can extract from this system. $$v_{\ast }(s)=\underset{\pi }{\max }{v}_{\pi }(s)$$
  • Similarly, optimal action value function is the maximum action value over all policies. $$q_{\ast }(s,a)=\underset{\pi }{\max }{q}_{\pi }(s,a)$$
  • Once you have these, you basically have the optimal policy, which is: in every state, take optimal action according to the optimal action value function.
    • An optimal policy can be found by maximizing over $q_{\ast }(s,a)$, $${\pi }_{\ast }(a\mid s)=\{\begin{array}{ll}1& \text{ if }a=\underset{a\in \mathcal{A}}{\mathrm{argmax}}{q}_{\ast }(s,a)\\ 0& \text{ otherwise }\end{array}$$
  • A deterministic optimal policy always exists for every MDP.
    • All optimal policies extract the optimal state value from the system and achieve the optimal action value.

Bellman optimality equation

(We basically substitute all $\pi$ with $\ast$ and all ${\sum }_{a\in \mathcal{A}}\pi (a\mid s)$ with ${\max }_a$ from the per policy equations)

$$q_{\ast }(s,a)={\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\ast }\left(s^{\prime }\right)$$ $$v_{\ast }(s)=\underset{a}{\max }{q}_{\ast }(s,a)$$

which gives

$$v_{\ast }(s)=\underset{a}{\max }\left[{\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\ast }\left(s^{\prime }\right)\right]$$

and

$$q_{\ast }(s,a)={\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}\left[{\mathcal{P}}_{s{s}^{\prime }}^a\underset{a^{\prime }}{\max }{q}_{\ast }\left(s^{\prime },a^{\prime }\right)\right]$$

• Earlier equations were linear and could be solved by solving matrix linear system because they involved summation instead of max. But with max, these equations are non linear and don’t have a general solution, and would need iterative solutions. Some methods to solve these include:
  • Value iteration
  • Policy iteration
  • Q-learning
  • Sarsa
• Extensions to MDPs:
  • Infinite and continuous
  • Partially observable
  • Undiscounted, average reward MDPs