import numpy as np import pytest from gridworld import GridWorld from qlearning import epsilon_greedy, greedy_rollout, q_learning from value_iteration import value_iteration GAMMA = 0.95 @pytest.mark.parametrize("seed", range(5)) def test_q_learning_converges_to_value_iteration(seed: int) -> None: env = GridWorld() v_star, q_star, _ = value_iteration(env, GAMMA) res = q_learning(env, episodes=5000, alpha=0.5, gamma=GAMMA, epsilon_start=1.0, epsilon_end=0.2, seed=seed) nonterminal = [s for s in range(env.n_states) if not env.is_terminal(s)] v_learned = res.q.max(axis=1) assert np.max(np.abs(v_learned[nonterminal] - v_star[nonterminal])) < 1e-3 assert np.max(np.abs(res.q[nonterminal] - q_star[nonterminal])) < 1e-2 # The greedy action is optimal in every non-terminal state (ties allowed). greedy = np.argmax(res.q, axis=1) for s in nonterminal: assert q_star[s, greedy[s]] == pytest.approx(v_star[s], abs=1e-6) def test_greedy_rollout_is_shortest_path() -> None: env = GridWorld() res = q_learning(env, seed=0) path, ret = greedy_rollout(env, res.q) assert env.char(path[-1]) == "G" assert len(path) - 1 == 8 and ret == pytest.approx(3.0) def test_same_seed_same_result() -> None: env = GridWorld() a = q_learning(env, episodes=200, seed=7) b = q_learning(env, episodes=200, seed=7) assert np.array_equal(a.q, b.q) and np.array_equal(a.returns, b.returns) def test_epsilon_greedy_frequencies() -> None: rng = np.random.default_rng(1) q_row = np.array([0.0, 1.0, 0.0, 0.0]) picks = np.array([epsilon_greedy(q_row, 0.2, rng) for _ in range(20_000)]) # Greedy action: 1 - eps + eps/4 = 0.85; each other action eps/4 = 0.05. assert np.mean(picks == 1) == pytest.approx(0.85, abs=0.01) assert np.mean(picks == 0) == pytest.approx(0.05, abs=0.01)