CSE510 Deep Reinforcement Learning (Lecture 4)

Markov Decision Process (MDP) Part II

Recall from last lecture

An Finite MDP is defined by:

• A finite set of states $s \in S$
• A finite set of actions $a \in A$
• A transition function $T(s, a, s')$
  • Probability that a from s leads to $s'$, i.e., $P(s'| s, a)$
  • Also called the model or the dynamics
• A reward function $R(s)$ ( Sometimes $R(s,a)$ or $R(s, a, s')$ )
• A start state
• Maybe a terminal state

A model for sequential decision making problem under uncertainty

Optimal Policy and Bellman Optimality Equation

The goal for a MDP is to compute or learn an optimal policy.

• An optimal policy is one that achieves the highest value at any state

• We define the optimal value function using Bellman Optimality Equation

• The optimal policy is

The Existence of the Optimal Policy

Theorem: for any Markov Decision Process

• There exists an optimal policy
• There can be many optimal policies, but all optimal policies achieve the same optimal value function
• There is always a deterministic optimal policy for any MDP

Solve MDP

Value Iteration

Repeatedly update an estimate of the optimal value function according to Bellman Optimality Equation.

1. Initialize an estimate for the value function arbitrarily

2. Repeat, update:

The general algorithm can be written as:

# suppose we defined the grid as previous example
 
grid = [
    [0, 0, 0, 1],
    [0, '*', 0, -100],
    [0, 0, 0, 0]
]
m,n = len(grid), len(grid[0])
ACTIONS = {'up':(0,-1), 'down':(0,1), 'left':(-1,0), 'right':(1,0)}
 
gamma = 0.9
V = value_iteration(gamma, ACTIONS, grid)
print(V)
 
def get_reward(action, i, j):
    reward = 0
    reward += 0.8 * grid[i+action[0]][j+action[1]] if i+action[0] >= 0 and i+action[0] < m and j+action[1] >= 0 and j+action[1] < n and grid[i+action[0]][j+action[1]] != '*' else grid[i][j]
    reward += 0.1 * grid[i+action[0]][j+action[1]] if i+action[0] >= 0 and i+action[0] < m and j+action[1] >= 0 and j+action[1] < n and grid[i+action[0]][j+action[1]] != '*' else grid[i][j]
    reward += 0.1 * grid[i+action[0]][j+action[1]] if i+action[0] >= 0 and i+action[0] < m and j+action[1] >= 0 and j+action[1] < n and grid[i+action[0]][j+action[1]] != '*' else grid[i][j]
    return reward
 
def value_iteration(gamma, ACTIONS, V):
    V_new=[[0]*m for _ in range(n)]
    while True:
        for i in range(m):
            for j in range(n):
                s = (i, j)
                V_new[i][j] = V[i][j] + gamma * max(get_reward(action, i, j) for action.values() in ACTIONS)
        if max(abs(V_new[i][j] - V[i][j]) for i in range(m) for j in range(n)) < 1e-6:
            break
        V = V_new
    return V

Convergence of Value Iteration

Theorem: Value Iteration converges to the optimal value function $\hat{V}\to V^*$ as $t\to\infty$.

Assume $0\leq \gamma < 1$, and reward $R(s)$ is bounded by $R_{\max}$.

Then

Let $V^k$ be the value function after $k$ iterations of Value Iteration.

Stopping condition

We can construct the optimal policy arbitrarily close to the optimal value function.

If $\|V^k-V^{k+1}\|<\epsilon$, then $\|V^k-V^*\|\leq \epsilon\frac{\gamma}{1-\gamma}$.

So we can select small $\epsilon$ to stop the iteration.

Greedy Policy

Given a $V^k$ that is close to the optimal value $V^*$, the greedy policy is:

Here $T(s',a,s')$ is the transition function between state $s'$ and $s$ with action $a$.

This selects the action looks best if we assume that we get value $V^k$ in one step.

Value of a greedy policy

If we define $V_g$ to be the value function of the greedy policy, then

This is not necessarily optimal, but it is a good approximation.

In homework, we will prove that if $\|V^k-V^*\|<\lambda$, then $\|V_g-V^*\|\leq 2\lambda\frac{\gamma}{1-\gamma}$.

So we can set stopping condition so that $V_g$ has desired accuracy to $V^*$.

There is a finite $\epsilon$ such that greedy policy is $\epsilon$-optimal.

Problem of Value Iteration and Policy Iteration

• It is slow $O(|S|^2|A|)$
• The max action at each state rarely changes
• The policy converges before the value function

Policy Iteration

Interleaving polity evaluation and policy improvement.

1. Initialize a random policy $\hat{\pi}$
2. Compute the value function $V^{\pi}$
3. Update the policy $\pi$ to be greedy policy with respect to $V^{\pi}$ $$\pi(s)\gets \arg\max_{a\in A} \sum_{s'\in S} P(s'|s,a) V^{\pi}(s')$$
4. Repeat until convergence

Exact Policy Evaluation by Linear Solver

Let $V^{\pi}\in \mathbb{R}^{|S|}$ be a vector of values for each state, $r\in \mathbb{R}^{|S|}$ be a vector of rewards for each state.

Let $P^{\pi}\in \mathbb{R}^{|S|\times |S|}$ be a transition matrix for the policy $\pi$.

The Bellman equation for the policy can be written in vector form as:

• Proof involves showing that each iteration is also a contraction and monotonically improve the policy
• Convergence to the exact optimal policy
  • The number of policies is finite

In real world, policy iteration is usually faster than value iteration.

Policy Iteration Complexity

• Each iteration runs in polynomial time in the number of states and actions
• There are at most |A|n policies and PI never repeats a policy
  • So at most an exponential number of iterations
  • Not a very good complexity bound
• Empirically O(n) iterations are required
  • Challenge: try to generate an MDP that requires more than that n iterations

Generalized Policy Iteration

• Generalized Policy Iteration (GPI): any interleaving of policy evaluation and policy improvement
• independent of their granularity and other details of the two processes

Summary

Policy Iteration vs Value Iteration

• PI has two loops: inner loop (evaluate $V^{\pi}$) and outer loop (improve $\pi$)

• VI has one loop: repeatedly apply $V^{k+1}(s) = \max_{a\in A} [r(s,a) + \gamma \sum_{s'\in S} P(s'|s,a) V^k(s')]$

• Trade-offs:

  • PI converges in few outer steps if you can evaluate quickly/accurately;
  • VI avoids expensive exact evaluation, doing cheaper but many Bellman optimality updates.

• Modified Policy Iteration: partial evaluation + improvement.

• Modified Policy Iteration: partial evaluation + improvement.