"""Tabular Q-learning with epsilon-greedy exploration (model-free).""" from __future__ import annotations from dataclasses import dataclass import numpy as np from gridworld import GridWorld def epsilon_greedy(q_row: np.ndarray, epsilon: float, rng: np.random.Generator) -> int: """Random action with probability epsilon, else a greedy action (ties broken at random).""" if rng.random() < epsilon: return int(rng.integers(len(q_row))) best = np.flatnonzero(q_row == q_row.max()) return int(rng.choice(best)) @dataclass class QLearningResult: q: np.ndarray # learned action values, shape (n_states, n_actions) returns: np.ndarray # undiscounted return of each training episode lengths: np.ndarray # steps per training episode snapshots: list[np.ndarray] # copies of Q every snapshot_every episodes (may be empty) def q_learning(env: GridWorld, episodes: int = 3000, alpha: float = 0.5, gamma: float = 0.95, epsilon_start: float = 1.0, epsilon_end: float = 0.1, decay_episodes: int | None = None, max_steps: int = 100, seed: int = 0, snapshot_every: int = 0) -> QLearningResult: """Learn Q from sampled transitions only. Epsilon falls linearly from epsilon_start to epsilon_end over decay_episodes (default: half of the episodes) and then stays at epsilon_end. Set both to the same value for a constant epsilon. """ rng = np.random.default_rng(seed) q = np.zeros((env.n_states, env.n_actions)) decay = decay_episodes if decay_episodes is not None else max(1, episodes // 2) returns = np.zeros(episodes) lengths = np.zeros(episodes, dtype=int) snapshots: list[np.ndarray] = [] for ep in range(episodes): frac = min(1.0, ep / decay) eps = epsilon_start + frac * (epsilon_end - epsilon_start) s = env.reset() total = 0.0 for t in range(max_steps): a = epsilon_greedy(q[s], eps, rng) s2, r, done = env.step(s, a, rng) target = r if done else r + gamma * q[s2].max() q[s, a] += alpha * (target - q[s, a]) # temporal-difference update total += r s = s2 if done: break returns[ep] = total lengths[ep] = t + 1 if snapshot_every and (ep + 1) % snapshot_every == 0: snapshots.append(q.copy()) return QLearningResult(q=q, returns=returns, lengths=lengths, snapshots=snapshots) def greedy_rollout(env: GridWorld, q: np.ndarray, max_steps: int = 100) -> tuple[list[int], float]: """Follow argmax Q from the start state in a deterministic world; return (states, return).""" s = env.reset() path = [s] total = 0.0 rng = np.random.default_rng(0) # only used if the world slips for _ in range(max_steps): s, r, done = env.step(s, int(np.argmax(q[s])), rng) path.append(s) total += r if done: break return path, total if __name__ == "__main__": from value_iteration import value_iteration env = GridWorld() v_star, q_star, _ = value_iteration(env, gamma=0.95) res = q_learning(env, episodes=3000, seed=0) v_learned = res.q.max(axis=1) nonterminal = [s for s in range(env.n_states) if not env.is_terminal(s)] err = np.max(np.abs(v_learned[nonterminal] - v_star[nonterminal])) print(f"V*(start) = {v_star[env.start]:.4f}, learned = {v_learned[env.start]:.4f}") print(f"max |V_learned - V*| over non-terminal states = {err:.2e}") path, ret = greedy_rollout(env, res.q) print(f"greedy path: {len(path) - 1} steps, return {ret:.1f}") print(env.render_policy(np.argmax(res.q, axis=1)))