Lesson 03 · Tabular RL

Balancing immediate and long-term goals

Policies, value functions and planning when the MDP is known.

The agent's goal is to maximise the expected return — the total reward it expects to collect. Future rewards are discounted by γ because "money today is worth more than money tomorrow".

The example uses value iteration to find the best policy for FrozenLake. Even the optimal policy only succeeds about 3 times in 4, because the ice is slippery.

Gₜ = rₜ₊₁ + γ·rₜ₊₂ + γ²·rₜ₊₃ + … V^π(s) = E_π[ Gₜ | sₜ = s ] value of a state Q^π(s,a) = E_π[ Gₜ | sₜ = s, aₜ = a ] value of an action in a state A^π(s,a) = Q^π(s,a) − V^π(s) how much better than average Bellman: V^π(s) = Σₐ π(a|s) Σₛ' T(s'|s,a) [ R + γ·V^π(s') ]

A policy (π) is "a plan for every situation" — deterministic or stochastic
Policy evaluation: compute V for a given policy
Policy improvement: build a new policy that is greedy with respect to V
Policy / value iteration: alternate the two steps until nothing changes. Value iteration truncates evaluation to one sweep, so it is faster
GPI: every method in the rest of the series is some form of "evaluate ↔ improve"

Key takeaways

V values states, Q values actions, A says how much better than average an action is
If the MDP is known, value/policy iteration finds π* directly (planning)

deep-rl-ep03-value-iteration.py

import numpy as np
import gymnasium as gym

def value_iteration(P, gamma=0.99, theta=1e-10):
    n_s, n_a = len(P), len(P[0])
    V = np.zeros(n_s)
    while True:
        Q = np.zeros((n_s, n_a))
        for s in range(n_s):
            for a in range(n_a):
                for prob, s2, r, done in P[s][a]:
                    Q[s, a] += prob * (r + gamma * V[s2] * (not done))
        if np.max(np.abs(V - Q.max(axis=1))) < theta:
            break
        V = Q.max(axis=1)                 # Bellman optimality backup
    pi = Q.argmax(axis=1)                 # ນະໂຍບາຍ greedy
    return V, pi

env = gym.make("FrozenLake-v1", is_slippery=True)
V, pi = value_iteration(env.unwrapped.P)
print(np.round(V.reshape(4, 4), 3))
print("π* =", "".join("←↓→↑"[a] for a in pi))

# ທົດສອບນະໂຍບາຍ 1,000 ເກມ
wins = 0
for ep in range(1000):
    s, _ = env.reset(seed=ep)
    done = False
    while not done:
        s, r, term, trunc, _ = env.step(pi[s])
        done = term or trunc
    wins += r
print(f"ອັດຕາສຳເລັດ: {wins / 10:.1f}%")

Output

[[0.542 0.499 0.471 0.457]
 [0.558 0.    0.358 0.   ]
 [0.592 0.643 0.615 0.   ]
 [0.    0.742 0.863 0.   ]]
π* = ←↑↑↑←←←←↑↓←←←→↓←
ອັດຕາສຳເລັດ: 75.5%

#DeepRL
#ReinforcementLearning
#PythonສຳລັບຄົນLaos
#AI
#ບອກຕໍ່ຄວາມຮູ້

Main Menu

Change Language

Currency

Balancing immediate and long-term goals

Key takeaways