xDev Asia

Bellman equation. Policy evaluation, policy improvement. Value iteration algorithm. GridWorld implementation in Python.

Reinforcement Learning: From Basics to Advanced

Part 1: RL Foundation — Markov Decision Process & Tabular Methods

xdev.asia

Introduction

Dynamic Programming (DP) solves MDP knowing the entire model — transition probabilities P(s'|s,a) and reward R. This is the theoretical foundation for all RL algorithms.

1. Bellman Equation

Bellman Expectation Equation

$$V^\pi(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^\pi(s')]$$

Bellman Optimality Equation

$$V^(s) = \max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^(s')]$$

2. Policy Evaluation

Calculate V(s) for a fixed policy:

import numpy as np

def policy_evaluation(policy, env, gamma=0.99, theta=1e-8):
    V = np.zeros(env.nS)
    while True:
        delta = 0
        for s in range(env.nS):
            v = 0
            for a, action_prob in enumerate(policy[s]):
                for prob, next_state, reward, done in env.P[s][a]:
                    v += action_prob * prob * (reward + gamma * V[next_state])
            delta = max(delta, abs(V[s] - v))
            V[s] = v
        if delta < theta:
            break
    return V

3. Policy Improvement

Greedy improvement based on V(s):

def policy_improvement(V, env, gamma=0.99):
    policy = np.zeros([env.nS, env.nA])
    for s in range(env.nS):
        q_values = np.zeros(env.nA)
        for a in range(env.nA):
            for prob, next_state, reward, done in env.P[s][a]:
                q_values[a] += prob * (reward + gamma * V[next_state])
        best_action = np.argmax(q_values)
        policy[s][best_action] = 1.0
    return policy

4. Policy Iteration

def policy_iteration(env, gamma=0.99):
    policy = np.ones([env.nS, env.nA]) / env.nA  # Uniform random
    while True:
        V = policy_evaluation(policy, env, gamma)
        new_policy = policy_improvement(V, env, gamma)
        if np.array_equal(policy, new_policy):
            break
        policy = new_policy
    return policy, V

5. Value Iteration

def value_iteration(env, gamma=0.99, theta=1e-8):
    V = np.zeros(env.nS)
    while True:
        delta = 0
        for s in range(env.nS):
            v = V[s]
            V[s] = max(
                sum(p * (r + gamma * V[s_])
                    for p, s_, r, _ in env.P[s][a])
                for a in range(env.nA)
            )
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    return V

6. GridWorld Demo

import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=False)
policy, V = policy_iteration(env.unwrapped, gamma=0.99)

print("Optimal Value Function:")
print(V.reshape(4, 4))
print("Optimal Policy (0=L, 1=D, 2=R, 3=U):")
print(np.argmax(policy, axis=1).reshape(4, 4))

Summary

Method	Approach	Convergence	Complexity
Policy Iteration	Evaluate → Improve	Few iterations	O(S²A) per evaluation
Value Iteration	One-step lookahead	Many iterations	O(SA) per iteration

Lesson 2: Dynamic Programming — Policy Iteration & Value Iteration