"""Murphy (2023), Chapter 35: Reinforcement learning.

Companion code for Chapter 35 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 1145-1183, written from scratch with numpy (scipy for the linear
algebra and optimisation helpers), to be read next to the lecture notes (../ch35-reinforcement-learning.html).
Markov decision processes, the Bellman equations, value iteration and bandits are in Chapter 34
(ch34_decision_making.py); this module starts from there.

Methods
* 35.1 exploration: epsilon-greedy and Boltzmann policies (Table 35.2), count-based optimism, and the
  Bayes-adaptive MDP solved by dynamic programming over the belief state (eps_greedy, boltzmann, table_35_2,
  bamdp_solve).
* 35.2 value-based RL: Monte Carlo control, TD(0), TD(lambda) with eligibility traces, SARSA, Q-learning and
  double Q-learning (td_lambda_walk, q_learning_trace, maxbias_experiment; Figures 35.4 and 35.5, own Figure 35.12).
* 35.3 policy-based RL: the policy gradient theorem on a tabular softmax policy, REINFORCE with and without a
  baseline, generalised advantage estimation, the performance difference lemma, conservative policy
  iteration and TRPO bounds, natural gradient, the PPO clip, the deterministic policy gradient on a
  linear-quadratic problem (pg_exact, reinforce_batch, cpi_bound_path; own Figures 35.13 and 35.15).
* 35.4 model-based RL: model predictive control with a terminal value, finite-horizon LQR (Riccati recursion),
  the moments of a Gaussian-process prediction at a Gaussian input, common random numbers (mpc_policy, lqr_riccati,
  gp_gaussian_input; own Figure 35.16).
* 35.5 off-policy learning: importance sampling, per-decision importance sampling, doubly robust estimation, the
  curse of horizon, the stationary distribution ratio, and linear TD under off-policy data (Baird's
  counterexample) (ope_experiment, baird_*; Figure 35.10, own Figure 35.14).
* 35.6 control as inference: soft value iteration (maximum-entropy RL), the exact message-passing policy,
  maximum-entropy inverse RL on an enumerated trajectory set, behaviour cloning and f-divergences
  (soft_value_iteration; own Figure 35.17).

Skipped figures, with reasons: Figures 35.1 and 35.3 (diagrams), 35.2 (backup diagrams), 35.6 (search tree),
35.7 and 35.9 (photographs and screenshots of robots and simulators), 35.8 (architecture of a learned world
model, trained on video frames: a large model) and 35.11 (a graphical model) contain nothing computed.
Figure 35.10(a) is a diagram of the seven-state MDP; panel (b) is reproduced.

Stand-ins (stated in the captions): Figure 35.4 uses my own random exploration sequence on the same
deterministic grid world (the book shows one hand-written sequence); Figure 35.5 averages 4000 runs instead
of 10,000 and uses eight actions in state B. Numbers 35.12 to 35.17 are my own extra figures.
"""
import json
import os
import sys

import numpy as np

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from common import BLUE, GREEN, GREY, MAGENTA, ORANGE, PURPLE, RED, CYAN, plt, savefig, run  # noqa: E402

CH = 35
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")


# ====================================================================== tabular MDP tools
class MDP:
    """A finite MDP: P[a, s, s'] transition probabilities, R[s, a] expected rewards, discount gamma."""

    def __init__(self, P, R, gamma):
        self.P = np.asarray(P, float)
        self.R = np.asarray(R, float)
        self.gamma = float(gamma)
        self.A, self.S = self.P.shape[0], self.P.shape[1]


def random_mdp(S=5, A=3, gamma=0.9, seed=0, conc=0.5):
    """A random MDP: transition rows Dirichlet(conc), rewards uniform on [0, 1]."""
    rng = np.random.default_rng(seed)
    P = rng.dirichlet(np.ones(S) * conc, size=(A, S))
    R = rng.uniform(0, 1, size=(S, A))
    return MDP(P, R, gamma)


def grid_1d(gamma=0.9):
    """The deterministic one-dimensional grid world of Murphy (2023), Figure 34.13.

    States 0, 1, 2 are S1, S2, S3; states 3 and 4 are the absorbing ST1 and ST2. Actions 0 = up, 1 = down.
    Going down from S3 enters ST2 with reward 1; going up from S1 enters ST1 with reward 0."""
    P = np.zeros((2, 5, 5))
    R = np.zeros((5, 2))
    for s in range(3):
        P[0, s, s - 1 if s > 0 else 3] = 1.0
        P[1, s, s + 1 if s < 2 else 4] = 1.0
    R[2, 1] = 1.0
    P[:, 3, 3] = 1.0
    P[:, 4, 4] = 1.0
    return MDP(P, R, gamma)


def policy_pr(mdp, pi):
    """State-to-state matrix P_pi and reward vector r_pi of a stochastic policy pi[s, a]."""
    Ppi = np.einsum("sa,ast->st", pi, mdp.P)
    rpi = (pi * mdp.R).sum(1)
    return Ppi, rpi


def evaluate(mdp, pi):
    """V_pi and Q_pi by solving the Bellman linear system (34.88)."""
    Ppi, rpi = policy_pr(mdp, pi)
    V = np.linalg.solve(np.eye(mdp.S) - mdp.gamma * Ppi, rpi)
    Q = mdp.R + mdp.gamma * np.einsum("ast,t->sa", mdp.P, V)
    return V, Q


def optimal(mdp, tol=1e-13, maxit=100000):
    """Q_*, V_* by value iteration to a tiny tolerance."""
    V = np.zeros(mdp.S)
    for _ in range(maxit):
        Q = mdp.R + mdp.gamma * np.einsum("ast,t->sa", mdp.P, V)
        V2 = Q.max(1)
        if np.max(np.abs(V2 - V)) < tol:
            V = V2
            break
        V = V2
    Q = mdp.R + mdp.gamma * np.einsum("ast,t->sa", mdp.P, V)
    return Q, V


def greedy(Q):
    """Deterministic greedy policy as a (S, A) one-hot matrix (ties to the lowest index)."""
    pi = np.zeros_like(Q)
    pi[np.arange(Q.shape[0]), Q.argmax(1)] = 1.0
    return pi


def eps_greedy(Q, eps):
    """The epsilon-greedy policy pi_eps (Section 35.1.5.1) as an (S, A) matrix."""
    A = Q.shape[1]
    return (1 - eps) * greedy(Q) + eps / A


def boltzmann(Q, tau):
    """The Boltzmann policy (35.1) as an (S, A) matrix."""
    z = (Q - Q.max(1, keepdims=True)) / tau
    e = np.exp(z)
    return e / e.sum(1, keepdims=True)


def occupancy(mdp, pi, p0):
    """Normalised discounted state and state-action occupancy (34.94)."""
    Ppi, _ = policy_pr(mdp, pi)
    d = (1 - mdp.gamma) * np.linalg.solve(np.eye(mdp.S) - mdp.gamma * Ppi.T, p0)
    return d, d[:, None] * pi


def objective(mdp, pi, p0):
    """J(pi) = E_{p0}[V_pi(s0)] (35.15)."""
    V, _ = evaluate(mdp, pi)
    return float(p0 @ V)


def softmax_rows(theta):
    e = np.exp(theta - theta.max(1, keepdims=True))
    return e / e.sum(1, keepdims=True)


def pg_exact(mdp, theta, p0):
    """The exact gradient of J for a tabular softmax policy from the policy gradient theorem (35.21):
    dJ/dtheta[s, b] = d(s) pi(b|s) A(s, b) / (1 - gamma)."""
    pi = softmax_rows(theta)
    V, Q = evaluate(mdp, pi)
    d, _ = occupancy(mdp, pi, p0)
    A = Q - V[:, None]
    return d[:, None] * pi * A / (1 - mdp.gamma)


# ====================================================================== 35.1 exploration
def table_35_2():
    """Rows of Table 35.2: epsilon-greedy (eps = 0.1) and Boltzmann (tau = 1) policies for two actions.

    Returns the list of (R1, R2, pi_eps(a1), pi_eps(a2), pi_tau(a1), pi_tau(a2)), unrounded."""
    rows = []
    for r1, r2 in [(1, 9), (4, 6), (4.9, 5.1), (5.05, 4.95), (7, 3), (8, 2)]:
        Q = np.array([[r1, r2]], float)
        pe = eps_greedy(Q, 0.1)[0]
        pt = boltzmann(Q, 1.0)[0]
        rows.append((r1, r2, pe[0], pe[1], pt[0], pt[1]))
    return rows


def known_theta_value(theta, h, safe=0.4):
    """Optimal value (and first action, 1 = try) at state 0 with h steps to go when theta is known."""
    V = [0.0]
    act = None
    for k in range(1, h + 1):
        v_safe = safe + V[-1]
        v_try = theta * (k - 1) + (1 - theta) * V[-1]
        act = int(v_try > v_safe)
        V.append(max(v_safe, v_try))
    return V[h], act


def bamdp_solve(H=10, safe=0.4):
    """Bayes-adaptive solution of a small MDP with an unknown transition probability (Section 35.1.5.4).

    State 0: action 'safe' (0) pays `safe` and stays; action 'try' (1) pays 0 and moves to state 1 with probability
    theta (unknown, Beta(a, b) belief), otherwise stays. State 1 is absorbing and pays 1 per step. Undiscounted,
    horizon H. The BAMDP state at state 0 is (h, a, b) with h steps to go. Returns V0(h, a, b), the action rule
    act(h, a, b) and the value of 'always safe'."""
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def V0(h, a, b):
        if h == 0:
            return 0.0
        th = a / (a + b)
        v_safe = safe + V0(h - 1, a, b)
        v_try = th * (h - 1) + (1 - th) * V0(h - 1, a, b + 1)
        return max(v_safe, v_try)

    def act(h, a, b):
        th = a / (a + b)
        return int(th * (h - 1) + (1 - th) * V0(h - 1, a, b + 1) > safe + V0(h - 1, a, b))
    return V0, act


def bamdp_simulate(policy, H, n, rng, a0=1.0, b0=1.0, safe=0.4, V0=None, act=None):
    """Average return of a policy in the BAMDP of bamdp_solve with theta drawn from the Beta(a0, b0) prior:
    'bayes' (the solution), 'ts' (Thompson sampling: solve the sampled MDP), 'plugin' (solve the MDP at the
    posterior mean), 'safe'."""
    tot = np.zeros(n)
    for i in range(n):
        theta = rng.beta(a0, b0)
        a, b, ret, state = a0, b0, 0.0, 0
        for t in range(H):
            h = H - t
            if state == 1:
                ret += 1.0
                continue
            if policy == "bayes":
                u = act(h, a, b)
            elif policy == "ts":
                u = known_theta_value(rng.beta(a, b), h, safe)[1]
            elif policy == "plugin":
                u = known_theta_value(a / (a + b), h, safe)[1]
            else:
                u = 0
            if u == 0:
                ret += safe
            elif rng.random() < theta:
                state = 1
            else:
                b += 1
        tot[i] = ret
    return float(tot.mean()), float(tot.std() / np.sqrt(n))


# ====================================================================== 35.2 value-based RL
def q_learning_trace(seed=279, episodes=5, eta=1.0, eps=0.5, gamma=0.9, max_len=30):
    """Tabular Q-learning with eta = 1 on the 1-D grid world, epsilon-greedy actions, as in Figure 35.4.

    Returns the list of Q tables (3 x 2 for S1..S3, columns up, down) at the start and after each episode, and the
    list of transitions (episode, step, s, a, r, s')."""
    rng = np.random.default_rng(seed)
    mdp = grid_1d(gamma)
    Q = np.zeros((5, 2))
    tables = [Q[:3].copy()]
    trans = []
    for ep in range(1, episodes + 1):
        s = 0
        for t in range(1, max_len + 1):
            if rng.random() < eps:
                a = int(rng.integers(2))
            else:
                a = int(np.argmax(Q[s] + 1e-9 * rng.random(2)))
            s2 = int(np.argmax(mdp.P[a, s]))
            r = mdp.R[s, a]
            trans.append((ep, t, s, a, r, s2))
            Q[s, a] += eta * (r + gamma * Q[s2].max() - Q[s, a])
            s = s2
            if s >= 3:
                break
        tables.append(Q[:3].copy())
    return tables, trans


def maxbias_experiment(runs=4000, episodes=300, n_b=8, alpha=0.1, eps=0.1, mu=-0.1, sigma=1.0, seed=0, estimates=False):
    """Q-learning versus double Q-learning on the maximisation-bias MDP of Figure 35.5.

    State A has actions left (to B, reward 0) and right (terminate, reward 0); state B has n_b actions that each
    terminate with reward N(mu, sigma^2). Returns the fraction of runs taking 'left' at A in every episode, for
    Q-learning and for double Q-learning, vectorised over runs."""
    out = {}
    for name in ("q", "dq"):
        rng = np.random.default_rng(seed)
        QA = np.zeros((2, runs, 2)); QB = np.zeros((2, runs, n_b))
        left_frac = np.zeros(episodes)
        est = np.zeros(episodes)
        ar = np.arange(runs)
        for ep in range(episodes):
            qa = QA[0] if name == "q" else QA[0] + QA[1]
            greedyA = np.argmax(qa + 1e-9 * rng.random((runs, 2)), axis=1)
            actA = np.where(rng.random(runs) < eps, rng.integers(2, size=runs), greedyA)
            go = actA == 0
            left_frac[ep] = go.mean()
            # state A update
            if name == "q":
                tgt = np.where(go, QB[0].max(1), 0.0)
                QA[0][ar, actA] += alpha * (tgt - QA[0][ar, actA])
            else:
                which = rng.integers(2, size=runs)               # which table to update
                for k in (0, 1):
                    m = which == k
                    nxt = np.argmax(QB[k] + 1e-9 * rng.random((runs, n_b)), axis=1)
                    tgt = np.where(go, QB[1 - k][ar, nxt], 0.0)
                    QA[k][ar[m], actA[m]] += alpha * (tgt[m] - QA[k][ar[m], actA[m]])
            # state B (only runs that went left)
            qb = QB[0] if name == "q" else QB[0] + QB[1]
            greedyB = np.argmax(qb + 1e-9 * rng.random((runs, n_b)), axis=1)
            actB = np.where(rng.random(runs) < eps, rng.integers(n_b, size=runs), greedyB)
            r = rng.normal(mu, sigma, size=runs)
            if name == "q":
                QB[0][ar[go], actB[go]] += alpha * (r[go] - QB[0][ar[go], actB[go]])
            else:
                which = rng.integers(2, size=runs)
                for k in (0, 1):
                    m = go & (which == k)
                    QB[k][ar[m], actB[m]] += alpha * (r[m] - QB[k][ar[m], actB[m]])
            # the value the method assigns to state B: max_b Q(B, b), or the cross-evaluated value for double Q
            if name == "q":
                est[ep] = QB[0].max(1).mean()
            else:
                a1 = QB[0].argmax(1); a2 = QB[1].argmax(1)
                est[ep] = 0.5 * (QB[1][ar, a1] + QB[0][ar, a2]).mean()
        out[name] = left_frac
        out[name + "_est"] = est
    return out


def td_lambda_walk(lam, alpha, n_states=19, episodes=10, runs=100, seed=0, gamma=1.0):
    """Online TD(lambda) with accumulating traces on the random walk with 19 states.

    The walk starts in the middle and moves left or right with probability 1/2; the left end pays -1, the right end +1.
    Returns the root-mean-square error over states, averaged over the first `episodes` episodes and over runs.
    Vectorised over runs."""
    rng = np.random.default_rng(seed)
    n = n_states
    true = (np.arange(1, n + 1) - (n + 1) / 2) / ((n + 1) / 2)
    v = np.zeros((runs, n + 2))                    # indices 0 and n+1 are terminal and stay 0
    err = np.zeros(episodes)
    ar = np.arange(runs)
    for ep in range(episodes):
        s = np.full(runs, (n + 1) // 2)
        e = np.zeros((runs, n + 2))
        active = np.ones(runs, bool)
        while active.any():
            step = np.where(rng.random(runs) < 0.5, -1, 1)
            s2 = s + step
            r = np.where(s2 == 0, -1.0, np.where(s2 == n + 1, 1.0, 0.0))
            delta = r + gamma * v[ar, s2] - v[ar, s]
            e *= gamma * lam
            e[ar, s] += 1.0
            upd = active[:, None]
            v += alpha * delta[:, None] * e * upd
            term = (s2 == 0) | (s2 == n + 1)
            s = np.where(term, (n + 1) // 2, s2)           # finished runs restart in the middle and are masked out
            active &= ~term
        err[ep] = np.sqrt(np.mean((v[:, 1:n + 1] - true) ** 2, axis=1)).mean()
    return err.mean()


# ====================================================================== 35.3 policy-based RL
def chain_mdp(n=6, gamma=0.95, offset=0.0):
    """A corridor with states 0..n-1 and actions left (0) and right (1); the end state n-1 pays 1 per step.

    Starts in state 0 (p0 = e_0). A constant `offset` is added to every reward, which does not change the
    optimal policy in a fixed-horizon problem but inflates the returns that REINFORCE multiplies by the score."""
    P = np.zeros((2, n, n)); R = np.zeros((n, 2))
    for s in range(n):
        P[0, s, max(s - 1, 0)] = 1.0
        P[1, s, min(s + 1, n - 1)] = 1.0
    R[n - 1, :] = 1.0
    R += offset
    return MDP(P, R, gamma)


def reinforce_batch(mdp, theta, batch, T, rng, baseline="none", w=None, p0=None, const=0.0):
    """One batch of REINFORCE gradient estimates (35.24, 35.25), vectorised over `batch` episodes of length T.

    Returns the per-episode gradient estimates (batch, S, A) of sum_t gamma^t (G_t - b) grad log pi(a_t | s_t),
    and the per-episode (s_t, G_t) arrays so that a baseline can be learned."""
    S, A = mdp.S, mdp.A
    pi = softmax_rows(theta)
    g = mdp.gamma
    s = np.zeros(batch, int) if p0 is None else rng.choice(S, size=batch, p=p0)
    ss = np.zeros((batch, T), int); aa = np.zeros((batch, T), int); rr = np.zeros((batch, T))
    cum = np.cumsum(pi, axis=1)
    for t in range(T):
        u = rng.random(batch)
        a = (u[:, None] > cum[s]).sum(1)
        a = np.minimum(a, A - 1)
        ss[:, t], aa[:, t] = s, a
        rr[:, t] = mdp.R[s, a]
        nxt = np.cumsum(mdp.P[a, s], axis=1)
        s = np.minimum((rng.random(batch)[:, None] > nxt).sum(1), S - 1)
    G = np.zeros((batch, T)); run_g = np.zeros(batch)
    for t in range(T - 1, -1, -1):
        run_g = rr[:, t] + g * run_g
        G[:, t] = run_g
    if baseline == "none":
        b = np.zeros((batch, T))
    elif baseline == "const":
        b = np.full((batch, T), const)
    else:                                                  # state baseline from a table w[s]
        b = w[ss]
    grads = np.zeros((batch, S, A))
    ar = np.arange(batch)
    for t in range(T):
        coef = (g ** t) * (G[:, t] - b[:, t])
        score = -pi[ss[:, t]]                              # d log pi(a|s)/d theta[s, b'] = 1[b' = a] - pi(b'|s)
        score[ar, aa[:, t]] += 1.0
        grads[ar, ss[:, t], :] += coef[:, None] * score
    return grads, ss, G


def reinforce_learning_curve(mdp, T, variant, iters=200, batch=10, eta=0.02, eta_w=0.1, runs=20, seed=0):
    """Learning curves of REINFORCE (Algorithm 35.2) with no baseline, a constant baseline or a learned state baseline.

    Returns the exact J(pi_theta) of the truncated problem is replaced by the infinite-horizon J (T is large enough),
    mean and standard deviation over runs, per iteration."""
    p0 = np.zeros(mdp.S); p0[0] = 1.0
    Js = np.zeros((runs, iters + 1))
    for r in range(runs):
        rng = np.random.default_rng(seed * 1000 + r)
        theta = np.zeros((mdp.S, mdp.A))
        w = np.zeros(mdp.S); cst = 0.0
        Js[r, 0] = objective(mdp, softmax_rows(theta), p0)
        for it in range(iters):
            if variant == "const":
                gr, ss, G = reinforce_batch(mdp, theta, batch, T, rng, "const", const=cst)
                cst = 0.9 * cst + 0.1 * G[:, 0].mean()
            elif variant == "state":
                gr, ss, G = reinforce_batch(mdp, theta, batch, T, rng, "state", w=w)
                early = np.arange(T) < T // 4          # truncation of the return is negligible early on
                for s_ in range(mdp.S):
                    m = (ss == s_) & early[None, :]
                    if m.any():
                        w[s_] += eta_w * (G[m].mean() - w[s_])
            else:
                gr, ss, G = reinforce_batch(mdp, theta, batch, T, rng, "none")
            theta = theta + eta * gr.mean(0)
            Js[r, it + 1] = objective(mdp, softmax_rows(theta), p0)
    return Js


def cpi_bound_path(mdp, pi, pi2, p0, thetas):
    """The mixture path pi_theta = theta pi' + (1 - theta) pi: actual improvement, the linear term theta L(pi')
    and the conservative-policy-iteration bound (35.33)."""
    V, Q = evaluate(mdp, pi)
    A = Q - V[:, None]
    d, _ = occupancy(mdp, pi, p0)
    Ap = (pi2 * A).sum(1)                                # E_{pi'}[A_pi(s, a)]
    L = float(d @ Ap / (1 - mdp.gamma))
    eps = np.abs(Ap).max()
    J0 = objective(mdp, pi, p0)
    act, lin, bnd = [], [], []
    for th in thetas:
        pit = th * pi2 + (1 - th) * pi
        act.append(objective(mdp, pit, p0) - J0)
        lin.append(th * L)
        bnd.append(th * L - 2 * eps * mdp.gamma / (1 - mdp.gamma) ** 2 * th ** 2)
    return np.array(act), np.array(lin), np.array(bnd), L, eps


# ====================================================================== 35.4 model-based RL
def grid_mdp(gamma=0.9, slip=0.2, step=-0.04):
    """A 4 x 4 stochastic grid world: goal (reward +1) and pit (reward -1) cells are absorbing, one wall,
    moves slip to each side with probability slip/2. States are the free cells plus one absorbing state."""
    W, Hh = 4, 4
    wall = {(1, 1)}
    goal, pit = (3, 3), (3, 2)
    cells = [(x, y) for y in range(Hh) for x in range(W) if (x, y) not in wall]
    idx = {c: i for i, c in enumerate(cells)}
    S = len(cells)
    moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]          # up, right, down, left
    P = np.zeros((4, S, S)); R = np.zeros((S, 4))

    def go(c, m):
        x, y = c[0] + m[0], c[1] + m[1]
        if not (0 <= x < W and 0 <= y < Hh) or (x, y) in wall:
            return c
        return (x, y)
    for c in cells:
        i = idx[c]
        for a in range(4):
            if c in (goal, pit):
                P[a, i, i] = 1.0
                continue
            for b, pr in ((a, 1 - slip), ((a + 1) % 4, slip / 2), ((a - 1) % 4, slip / 2)):
                c2 = go(c, moves[b])
                P[a, i, idx[c2]] += pr
                R[i, a] += pr * (1.0 if c2 == goal else (-1.0 if c2 == pit else step))
    return MDP(P, R, gamma), cells, idx


def mpc_policy(mdp, H, Vhat):
    """The H-step receding-horizon policy of (35.46): greedy with respect to Q_H = R + gamma P (T*)^(H-1) Vhat."""
    U = np.asarray(Vhat, float).copy()
    for _ in range(H - 1):
        U = (mdp.R + mdp.gamma * np.einsum("ast,t->sa", mdp.P, U)).max(1)
    QH = mdp.R + mdp.gamma * np.einsum("ast,t->sa", mdp.P, U)
    return greedy(QH), U


def lqr_riccati(A, B, Q, Rr, QT, T):
    """Finite-horizon LQR by the backward Riccati recursion: costs sum_t x'Qx + u'Ru + x_T' QT x_T.

    Returns gains K_t (u_t = -K_t x_t) for t = 0..T-1 and the matrices P_t of V_t(x) = x' P_t x."""
    P = QT.copy()
    Ks = [None] * T
    Ps = [None] * (T + 1)
    Ps[T] = P
    for t in range(T - 1, -1, -1):
        K = np.linalg.solve(Rr + B.T @ P @ B, B.T @ P @ A)
        P = Q + A.T @ P @ (A - B @ K)
        Ks[t], Ps[t] = K, P
    return Ks, Ps


def gp_gaussian_input(X, y, mu, Sigma, lam, alpha2, noise2):
    """Mean and second moment of the GP posterior mean at a Gaussian input x ~ N(mu, Sigma), for the squared
    exponential kernel k(a, b) = alpha2 exp(-0.5 (a-b)' Lam^-1 (a-b)), Lam = diag(lam).

    Returns E[m(x)] = beta' q and E[m(x)^2] = beta' Q beta with beta = (K + noise2 I)^-1 y."""
    n, D = X.shape
    Lam = np.diag(lam)
    K = alpha2 * np.exp(-0.5 * (((X[:, None, :] - X[None, :, :]) ** 2) / lam).sum(-1))
    beta = np.linalg.solve(K + noise2 * np.eye(n), y)
    # q_i = int k(x_i, x) N(x | mu, Sigma) dx
    S1 = Sigma + Lam
    d = X - mu
    q = alpha2 * np.sqrt(np.linalg.det(np.eye(D) + Sigma @ np.linalg.inv(Lam))) ** -1 * np.exp(-0.5 * np.einsum("ni,ij,nj->n", d, np.linalg.inv(S1), d))
    # Q_ij = int k(x_i, x) k(x_j, x) N(x | mu, Sigma) dx
    Lh = Lam / 2
    zbar = 0.5 * (X[:, None, :] + X[None, :, :])
    dd = X[:, None, :] - X[None, :, :]
    pref = alpha2 ** 2 * np.exp(-0.25 * np.einsum("nmi,ij,nmj->nm", dd, np.linalg.inv(Lam), dd))
    dz = zbar - mu
    Sh = np.linalg.inv(Sigma + Lh)
    expo = np.exp(-0.5 * np.einsum("nmi,ij,nmj->nm", dz, Sh, dz))
    scale = np.sqrt(np.linalg.det(np.eye(D) + 2 * Sigma @ np.linalg.inv(Lam))) ** -1
    Qm = pref * expo * scale
    return float(beta @ q), float(beta @ Qm @ beta), beta, K


# ====================================================================== 35.5 off-policy learning
def ope_env(S=3, A=2, seed=3, pe_top=0.8):
    """A small random MDP with a target policy that picks action 0 with probability pe_top and a uniform behaviour policy."""
    rng = np.random.default_rng(seed)
    P = rng.dirichlet(np.ones(S), size=(A, S))
    R = rng.uniform(0, 1, size=(S, A))
    pe = np.full((S, A), (1 - pe_top) / (A - 1)); pe[:, 0] = pe_top
    pb = np.full((S, A), 1.0 / A)
    return P, R, pe, pb


def finite_horizon_q(P, R, pi, T, gamma):
    """Q^k(s, a) and V^k(s) for k = 0..T steps to go under pi (k = 0 is the zero function)."""
    S, A = R.shape
    Qs = [np.zeros((S, A))]
    Vs = [np.zeros(S)]
    for k in range(1, T + 1):
        Q = R + gamma * np.einsum("ast,t->sa", P, Vs[-1])
        Qs.append(Q)
        Vs.append((pi * Q).sum(1))
    return Qs, Vs


def sample_trajs(P, R, pb, n, T, rng, noise=0.1):
    """n trajectories of length T from the behaviour policy: states, actions, rewards (mean R plus noise)."""
    S, A = R.shape
    s = np.zeros(n, int)
    ss = np.zeros((n, T + 1), int); aa = np.zeros((n, T), int); rr = np.zeros((n, T))
    cb = np.cumsum(pb, axis=1)
    cP = np.cumsum(P, axis=2)
    ss[:, 0] = s
    for t in range(T):
        a = np.minimum((rng.random(n)[:, None] > cb[s]).sum(1), A - 1)
        rr[:, t] = R[s, a] + noise * rng.normal(size=n)
        s = np.minimum((rng.random(n)[:, None] > cP[a, s]).sum(1), S - 1)
        aa[:, t] = a
        ss[:, t + 1] = s
    return ss, aa, rr


def ope_estimates(ss, aa, rr, pe, pb, gamma, Qhat_fn=None, T=None):
    """IS (35.47), per-decision IS (35.49), self-normalised IS and doubly robust (35.53) estimates, one per trajectory
    (the self-normalised one is returned as a single number). Qhat_fn(k) gives (Qhat, Vhat) with k steps to go."""
    n, Tmax = aa.shape
    T = Tmax if T is None else T
    rho = pe[ss[:, :T], aa[:, :T]] / pb[ss[:, :T], aa[:, :T]]
    cprod = np.cumprod(rho, axis=1)
    disc = gamma ** np.arange(T)
    is_est = cprod[:, -1] * (rr[:, :T] * disc).sum(1)
    pdis = (cprod * rr[:, :T] * disc).sum(1)
    w = cprod[:, -1]
    wis = float((w * (rr[:, :T] * disc).sum(1)).sum() / w.sum())
    dr = None
    if Qhat_fn is not None:
        dr = np.zeros(n)
        Vhat0 = Qhat_fn(T)[1][ss[:, 0]]
        terms = np.zeros(n)
        for t in range(T):
            Qk, Vk = Qhat_fn(T - t)                         # Qhat_t(s, a): T - t steps to go
            Vn = Qhat_fn(T - t - 1)[1][ss[:, t + 1]] if T - t - 1 >= 0 else 0.0
            terms += cprod[:, t] * disc[t] * (rr[:, t] + gamma * Vn - Qk[ss[:, t], aa[:, t]])
        dr = Vhat0 + terms
    return is_est, pdis, wis, dr


def dr_recursive(ss, aa, rr, pe, pb, gamma, Qhat_fn, T):
    """The recursive form (35.52) of the doubly robust estimator, one value per trajectory."""
    n = aa.shape[0]
    J = np.zeros(n)                                         # J_DR[T] = 0
    for t in range(T - 1, -1, -1):
        Qk, Vk = Qhat_fn(T - t)
        rho = pe[ss[:, t], aa[:, t]] / pb[ss[:, t], aa[:, t]]
        J = Vk[ss[:, t]] + rho * (rr[:, t] + gamma * J - Qk[ss[:, t], aa[:, t]])
    return J


BAIRD_PHI = np.zeros((7, 8))
for _i in range(6):
    BAIRD_PHI[_i, _i] = 2.0
    BAIRD_PHI[_i, 7] = 1.0
BAIRD_PHI[6, 6] = 1.0
BAIRD_PHI[6, 7] = 2.0


def baird_matrices(gamma=0.99, mode="off"):
    """Matrices of the expected semi-gradient TD(0) update on Baird's counterexample (Figure 35.10(a)).

    off: data from the behaviour policy b (dashed 6/7, solid 1/7), evaluating the target pi (always solid): the
    state distribution is uniform and the expected update is -alpha A w with A = Phi' D (Phi - gamma P_pi Phi).
    on: the behaviour policy evaluates itself. Returns A and the state distribution."""
    D = np.eye(7) / 7.0
    Ppi = np.zeros((7, 7)); Ppi[:, 6] = 1.0                 # solid: to the bottom state
    if mode == "on":
        Ppi = np.zeros((7, 7)); Ppi[:, :6] = 1.0 / 7.0; Ppi[:, 6] = 1.0 / 7.0   # one step of b: uniform
    A = BAIRD_PHI.T @ D @ (BAIRD_PHI - gamma * Ppi @ BAIRD_PHI)
    return A, np.diag(D)


def baird_run(steps=1000, alpha=0.01, gamma=0.99, mode="sampled", behaviour="off", seed=0, w0=None):
    """Weights of semi-gradient TD(0) on Baird's counterexample over time.

    mode 'sampled': a trajectory from b with the importance ratio rho = pi/b (0 for dashed, 7 for solid);
    mode 'expected': the expected update. behaviour 'on' evaluates b with its own data (no ratio)."""
    w = np.array([1, 1, 1, 1, 1, 1, 10, 1], float) if w0 is None else np.array(w0, float)
    hist = [w.copy()]
    rng = np.random.default_rng(seed)
    if mode == "expected":
        A, _ = baird_matrices(gamma, "off" if behaviour == "off" else "on")
        for _ in range(steps):
            w = w - alpha * A @ w
            hist.append(w.copy())
        return np.array(hist)
    s = int(rng.integers(7))
    for _ in range(steps):
        solid = rng.random() < 1 / 7
        s2 = 6 if solid else int(rng.integers(6))
        rho = (7.0 if solid else 0.0) if behaviour == "off" else 1.0
        phi, phi2 = BAIRD_PHI[s], BAIRD_PHI[s2]
        delta = gamma * phi2 @ w - phi @ w
        w = w + alpha * rho * delta * phi
        hist.append(w.copy())
        s = s2
    return np.array(hist)


# ====================================================================== 35.6 control as inference
def soft_value_iteration(mdp, lam, tol=1e-12, maxit=100000):
    """Soft (maximum-entropy) value iteration for the discounted objective E sum gamma^t (R + lam H(pi)):
    Q = R + gamma E V', V = lam log sum_a exp(Q / lam), pi = exp((Q - V) / lam). Returns Q, V, pi."""
    V = np.zeros(mdp.S)
    for _ in range(maxit):
        Q = mdp.R + mdp.gamma * np.einsum("ast,t->sa", mdp.P, V)
        m = Q.max(1)
        V2 = m + lam * np.log(np.exp((Q - m[:, None]) / lam).sum(1))
        if np.max(np.abs(V2 - V)) < tol:
            V = V2
            break
        V = V2
    Q = mdp.R + mdp.gamma * np.einsum("ast,t->sa", mdp.P, V)
    pi = np.exp((Q - V[:, None]) / lam)
    return Q, V, pi / pi.sum(1, keepdims=True)


def policy_entropy_return(mdp, pi, p0, mask=None):
    """Expected discounted return J and the expected discounted entropy sum E sum gamma^t H(pi(s_t)); `mask`
    (1 for the states that count) leaves out absorbing states, where every action is equivalent."""
    d, _ = occupancy(mdp, pi, p0)
    H = -(pi * np.log(np.maximum(pi, 1e-300))).sum(1)
    if mask is not None:
        H = H * mask
    return objective(mdp, pi, p0), float(d @ H) / (1 - mdp.gamma)


# ====================================================================== figures
def fig_35_4(out=None):
    """Figure 35.4: tabular Q-learning with eta = 1 on the 1-D grid world: Q tables at the start and after episodes 1 to 5."""
    tables, trans = q_learning_trace()
    n = len(tables)
    fig, axes = plt.subplots(1, n, figsize=(1.55 * n + 0.4, 2.55))
    mdp = grid_1d(0.9)
    Qs, _ = optimal(mdp)
    for k, (ax, Qt) in enumerate(zip(axes, tables)):
        ax.imshow(Qt, cmap="Blues", vmin=0, vmax=1, aspect="auto")
        for i in range(3):
            for j in range(2):
                ax.text(j, i, "%.2f" % Qt[i, j], ha="center", va="center", fontsize=8.5,
                        color="white" if Qt[i, j] > 0.6 else "black")
        ax.set_xticks([0, 1]); ax.set_xticklabels(["up", "down"], fontsize=8)
        ax.set_yticks([0, 1, 2]); ax.set_yticklabels(["S1", "S2", "S3"] if k == 0 else [], fontsize=8)
        ax.set_title("start" if k == 0 else "end of ep. %d" % k, fontsize=8.5)
    fig.suptitle("$Q(s,a)$ after each episode; $Q_*$ down: %s, up: %s" % (
        ", ".join("%.2f" % x for x in Qs[:3, 1]), ", ".join("%.2f" % x for x in Qs[:3, 0])), fontsize=9, y=1.02)
    fig.tight_layout()
    savefig(fig, CH, "fig35-4", out)


def fig_35_5(out=None):
    """Figure 35.5: maximisation bias of Q-learning against double Q-learning (4000 runs, 8 actions in state B)."""
    res = maxbias_experiment()
    fig, ax = plt.subplots(figsize=(5.2, 3.3))
    x = np.arange(1, len(res["q"]) + 1)
    ax.plot(x, 100 * res["q"], color=RED, label="Q-learning")
    ax.plot(x, 100 * res["dq"], color=GREEN, label="double Q-learning")
    ax.axhline(5, color="black", ls="--", lw=1); ax.text(300, 6.5, "optimal (5%)", ha="right", fontsize=8)
    ax.set_xlabel("episodes"); ax.set_ylabel("% left actions from A"); ax.set_ylim(0, 100)
    ax.legend(frameon=False, fontsize=8.5)
    ax.set_title("$\\epsilon=0.1$, $\\alpha=0.1$, 8 actions in B, $r\\sim\\mathcal{N}(-0.1,1)$", fontsize=9)
    fig.tight_layout()
    savefig(fig, CH, "fig35-5", out)


def fig_35_10(out=None):
    """Figure 35.10(b): semi-gradient off-policy TD(0) diverges on Baird's counterexample; on-policy data do not."""
    fig, axes = plt.subplots(1, 3, figsize=(9.6, 3.0), sharey=False)
    cols = [BLUE, CYAN, GREEN, ORANGE, PURPLE, MAGENTA, RED, "black"]
    h1 = baird_run(1000, 0.01, mode="sampled", behaviour="off", seed=1)
    h2 = baird_run(1000, 0.01, mode="expected", behaviour="off")
    h3 = baird_run(1000, 0.01, mode="sampled", behaviour="on", seed=1)
    for ax, h, ttl in zip(axes, (h1, h2, h3), ("(a) sampled, off-policy", "(b) expected update, off-policy", "(c) on-policy (behaviour evaluates itself)")):
        for k in range(8):
            ax.plot(h[:, k], color=cols[k], lw=1.0, label="$w_%d$" % (k + 1))
        ax.set_title(ttl, fontsize=8.5); ax.set_xlabel("steps")
    axes[0].set_ylabel("weights")
    axes[0].legend(ncol=2, fontsize=7, frameon=False, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig35-10", out)


def fig_35_12(out=None):
    """Own Figure 35.12: TD(lambda) on the 19-state random walk: error against step size, and the best error against lambda."""
    lams = [0.0, 0.4, 0.8, 0.9, 0.95, 1.0]
    alphas = np.linspace(0.02, 1.0, 17)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.2))
    best = []
    for lam, c in zip(lams, [BLUE, CYAN, GREEN, ORANGE, RED, MAGENTA]):
        errs = np.array([td_lambda_walk(lam, a, runs=100, seed=5) for a in alphas])
        errs = np.where(errs > 0.7, np.nan, errs)
        axes[0].plot(alphas, errs, color=c, label="$\\lambda=%.2f$" % lam)
        best.append(np.nanmin(errs))
    axes[0].set_ylim(0.2, 0.6); axes[0].set_xlabel("step size $\\alpha$"); axes[0].set_ylabel("RMS error (first 10 episodes)")
    axes[0].legend(fontsize=7.5, frameon=False, ncol=2)
    lg = np.linspace(0, 1, 11)
    bl = []
    for lam in lg:
        errs = [td_lambda_walk(lam, a, runs=100, seed=5) for a in alphas]
        bl.append(np.nanmin(errs))
    axes[1].plot(lg, bl, "o-", color=BLUE, ms=4)
    axes[1].set_xlabel("$\\lambda$"); axes[1].set_ylabel("best RMS error over $\\alpha$")
    for ax, t in zip(axes, ("(a) error against $\\alpha$", "(b) intermediate $\\lambda$ wins")):
        ax.set_title(t, fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig35-12", out)


def reinforce_sd(mdp, T, variants, n=20000, seed=0):
    """Total standard deviation of the single-episode REINFORCE estimate at theta = 0, for several baselines."""
    rng = np.random.default_rng(seed)
    theta = np.zeros((mdp.S, mdp.A))
    p0 = np.zeros(mdp.S); p0[0] = 1
    exact = pg_exact(mdp, theta, p0)
    out = {}
    g0, ss0, G0 = reinforce_batch(mdp, theta, n, T, rng, "none")
    Vs = np.zeros(mdp.S)
    early = np.arange(T) < T // 4
    for s_ in range(mdp.S):
        m = (ss0 == s_) & early[None, :]
        Vs[s_] = G0[m].mean() if m.any() else 0.0
    for v in variants:
        if v == "none":
            g = g0
        elif v == "const":
            g, _, _ = reinforce_batch(mdp, theta, n, T, np.random.default_rng(seed + 1), "const", const=float(G0[:, 0].mean()))
        else:
            g, _, _ = reinforce_batch(mdp, theta, n, T, np.random.default_rng(seed + 2), "state", w=Vs)
        out[v] = (g.mean(0), float(np.sqrt(g.reshape(n, -1).var(0).sum())))
    return exact, out


def reinforce_sd_exact(mdp, T, n=20000, seed=0, const_from="start"):
    """Total standard deviation of the one-episode REINFORCE estimate at theta = 0 for the baselines none, the constant
    V_pi(s_0) and the exact V_pi(s); also the norm of the exact gradient."""
    rng = np.random.default_rng(seed)
    theta = np.zeros((mdp.S, mdp.A))
    p0 = np.zeros(mdp.S); p0[0] = 1
    Vpi, _ = evaluate(mdp, softmax_rows(theta))
    exact = pg_exact(mdp, theta, p0)
    res = {}
    for v, kw in (("none", {}), ("const", dict(const=float(Vpi[0]))), ("state", dict(w=Vpi))):
        g, _, _ = reinforce_batch(mdp, theta, n, T, rng, v, **kw)
        res[v] = float(np.sqrt(g.reshape(n, -1).var(0).sum()))
    return res, float(np.linalg.norm(exact))


def fig_35_13(out=None):
    """Own Figure 35.13: REINFORCE with no baseline, a constant baseline and a learned state baseline (Algorithm 35.2)."""
    mdp = chain_mdp(6, 0.9, offset=2.0)
    T = 80
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.2), gridspec_kw=dict(width_ratios=[1.35, 1]))
    p0 = np.zeros(mdp.S); p0[0] = 1
    Jopt = objective(mdp, greedy(optimal(mdp)[0]), p0)
    names = {"none": "no baseline", "const": "constant baseline", "state": "learned $V_w(s)$ baseline"}
    for v, c in zip(("none", "const", "state"), (RED, ORANGE, BLUE)):
        Js = reinforce_learning_curve(mdp, T, v, iters=150, batch=10, eta=0.05, runs=16, seed=1)
        m, sd = Js.mean(0), Js.std(0)
        x = np.arange(len(m))
        axes[0].plot(x, m, color=c, label=names[v])
        axes[0].fill_between(x, m - sd, m + sd, color=c, alpha=0.18, lw=0)
    axes[0].axhline(Jopt, color="black", ls="--", lw=0.9)
    axes[0].set_xlabel("iteration (10 episodes each)"); axes[0].set_ylabel("expected return $J(\\pi_\\theta)$")
    axes[0].legend(frameon=False, fontsize=8, loc="lower right"); axes[0].set_title("(a) learning curves, 16 runs", fontsize=9.5)
    exact, res = reinforce_sd(mdp, T, ("none", "const", "state"))
    sds = [res[v][1] for v in ("none", "const", "state")]
    axes[1].bar(range(3), sds, color=[RED, ORANGE, BLUE])
    axes[1].set_xticks(range(3)); axes[1].set_xticklabels(["none", "constant", "$V_w(s)$"])
    axes[1].set_yscale("log"); axes[1].set_ylabel("std. dev. of one-episode gradient")
    axes[1].set_title("(b) estimator spread at $\\theta=0$", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig35-13", out)


def fig_35_14(out=None):
    """Own Figure 35.14: the curse of horizon: root-mean-square error of IS, PDIS, self-normalised IS and DR against the horizon."""
    P, R, pe, pb = ope_env()
    gamma = 0.99
    Tmax = 40
    Ts = [1, 2, 4, 6, 8, 10, 15, 20, 30, 40]
    Qk, Vk = finite_horizon_q(P, R, pe, Tmax + 1, gamma)

    def Qhat(k):                                            # a model that is off by a constant 0.3 per remaining step
        return Qk[k] + 0.3 * (1 - gamma ** k) / (1 - gamma) / 3.0, Vk[k] + 0.3 * (1 - gamma ** k) / (1 - gamma) / 3.0
    rng = np.random.default_rng(7)
    n, reps = 100, 200
    rm = {k: [] for k in ("IS", "PDIS", "WIS", "DR")}
    for T in Ts:
        errs = {k: [] for k in rm}
        truth = Vk[T][0]
        for r in range(reps):
            ss, aa, rr = sample_trajs(P, R, pb, n, T, rng)
            ise, pdis, wis, dr = ope_estimates(ss, aa, rr, pe, pb, gamma, Qhat, T)
            errs["IS"].append(ise.mean() - truth); errs["PDIS"].append(pdis.mean() - truth)
            errs["WIS"].append(wis - truth); errs["DR"].append(dr.mean() - truth)
        for k in rm:
            rm[k].append(np.sqrt(np.mean(np.square(errs[k]))))
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.2))
    for k, c in zip(rm, (RED, ORANGE, GREEN, BLUE)):
        axes[0].plot(Ts, rm[k], "o-", color=c, ms=3.5, label=k)
    axes[0].set_yscale("log"); axes[0].set_xlabel("horizon $T$"); axes[0].set_ylabel("RMSE of $\\hat J(\\pi_e)$ (100 trajectories)")
    axes[0].legend(frameon=False, fontsize=8.5); axes[0].set_title("(a) error against horizon", fontsize=9.5)
    Tg = np.arange(1, 41)
    e2 = float((pe ** 2 / pb).sum(1).mean())
    axes[1].semilogy(Tg, e2 ** Tg - 1, color=RED, label="$\\mathrm{var}\\,\\rho_{0:T-1}=m^T-1$")
    axes[1].set_xlabel("horizon $T$"); axes[1].set_title("(b) variance of the trajectory ratio", fontsize=9.5)
    axes[1].legend(frameon=False, fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig35-14", out)


def fig_35_15(out=None):
    """Own Figure 35.15: conservative policy iteration (35.33) and the TRPO-type bound on a random MDP."""
    mdp = random_mdp(6, 3, 0.7, seed=11)
    rng = np.random.default_rng(0)
    p0 = np.ones(mdp.S) / mdp.S
    pi = softmax_rows(rng.normal(size=(mdp.S, mdp.A)))
    Qs, _ = optimal(mdp)
    pi2 = greedy(Qs)
    th = np.linspace(0, 1, 101)
    act, lin, bnd, L, eps = cpi_bound_path(mdp, pi, pi2, p0, th)
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.3))
    axes[0].plot(th, act, color=BLUE, label="$J(\\pi_\\theta)-J(\\pi)$")
    axes[0].plot(th, lin, color=GREY, ls="--", label="linear term $\\theta L(\\pi')$")
    axes[0].plot(th, bnd, color=RED, label="bound (35.33)")
    axes[0].axhline(0, color="black", lw=0.6)
    axes[0].set_xlabel("mixing weight $\\theta$"); axes[0].legend(frameon=False, fontsize=8)
    axes[0].set_title("(a) mixture $\\pi_\\theta=\\theta\\pi'+(1-\\theta)\\pi$", fontsize=9.5)
    # (b) TRPO-type bound over random policy pairs
    gm = mdp.gamma
    xs, ys, bs = [], [], []
    for k in range(400):
        p1 = softmax_rows(rng.normal(size=(mdp.S, mdp.A)) * 1.2)
        p2 = softmax_rows(np.log(p1) + rng.normal(size=(mdp.S, mdp.A)) * rng.uniform(0.02, 0.6))
        V, Q = evaluate(mdp, p1)
        A = Q - V[:, None]
        d, _ = occupancy(mdp, p1, p0)
        Lp = float(d @ (p2 * A).sum(1) / (1 - gm))
        kl = float(((p1 * np.log(p1 / p2)).sum(1)).max())
        e = np.abs(A).max()
        gap = objective(mdp, p2, p0) - objective(mdp, p1, p0) - Lp
        xs.append(kl); ys.append(gap); bs.append(2 * e * gm / (1 - gm) ** 2 * kl)
    xs, ys, bs = map(np.array, (xs, ys, bs))
    axes[1].scatter(xs, np.abs(ys), s=8, color=BLUE, label="$|J(\\pi')-J(\\pi)-L(\\pi')|$")
    order = np.argsort(xs)
    axes[1].plot(xs[order], bs[order], color=RED, lw=1.0, label="$\\frac{2\\epsilon\\gamma}{(1-\\gamma)^2}\\max_s\\mathrm{KL}$")
    axes[1].set_xscale("log"); axes[1].set_yscale("log"); axes[1].set_xlabel("$\\max_s\\mathrm{KL}(\\pi(s)\\,\\|\\,\\pi'(s))$")
    axes[1].set_title("(b) 400 random policy pairs", fontsize=9.5); axes[1].legend(frameon=False, fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig35-15", out)


def fig_35_16(out=None):
    """Own Figure 35.16: model predictive control with a horizon H and a terminal value: loss against H and the bound."""
    mdp, cells, idx = grid_mdp()
    Qs, Vs = optimal(mdp)
    Hs = np.arange(1, 13)
    fig, ax = plt.subplots(figsize=(5.4, 3.3))
    for name, Vh, c in (("$\\hat V=0$", np.zeros(mdp.S), BLUE), ("$\\hat V=0.7V_*$", 0.7 * Vs, GREEN)):
        loss, bound = [], []
        for H in Hs:
            pi, U = mpc_policy(mdp, H, Vh)
            V, _ = evaluate(mdp, pi)
            loss.append(np.max(np.abs(V - Vs)))
            bound.append(2 * mdp.gamma ** H * np.max(np.abs(Vh - Vs)) / (1 - mdp.gamma))
        loss = np.array(loss)
        shown = np.where(loss > 1e-13, loss, 1e-13)
        ax.semilogy(Hs, shown, "o-", color=c, ms=3.5, label=name + ": $\\|V_{\\mathrm{MPC}}-V_*\\|_\\infty$")
        ax.semilogy(Hs, bound, ":", color=c, label=name + ": bound")
    ax.set_xlabel("planning horizon $H$"); ax.set_ylim(3e-14, 30)
    ax.text(12.4, 3e-13, "points on the bottom line: loss exactly 0", ha="right", fontsize=7.5)
    ax.legend(frameon=False, fontsize=7.5)
    ax.set_title("MPC on the stochastic grid world, $\\gamma=0.9$", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig35-16", out)


def fig_35_17(out=None):
    """Own Figure 35.17: maximum-entropy RL on the grid world: return, entropy and the policy as the temperature changes."""
    mdp, cells, idx = grid_mdp()
    p0 = np.ones(mdp.S) / mdp.S
    Qs, Vs = optimal(mdp)
    Jstar = objective(mdp, greedy(Qs), p0)
    lams = np.logspace(-3, 1, 25)
    Js, Hs = [], []
    mask = np.array([0.0 if c in ((3, 3), (3, 2)) else 1.0 for c in cells])
    for lam in lams:
        _, _, pi = soft_value_iteration(mdp, lam)
        J, H = policy_entropy_return(mdp, pi, p0, mask)
        Js.append(J); Hs.append(H)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.2))
    axes[0].semilogx(lams, Js, color=BLUE, label="expected return of $\\pi_\\lambda$")
    axes[0].axhline(Jstar, color="black", ls="--", lw=0.9, label="$J(\\pi_*)$")
    axes[0].set_xlabel("temperature $\\lambda$"); axes[0].set_ylabel("expected return")
    ax2 = axes[0].twinx(); ax2.semilogx(lams, Hs, color=RED); ax2.set_ylabel("discounted entropy, free cells", color=RED, fontsize=9)
    axes[0].plot([], [], color=RED, label="entropy (right axis)")
    axes[0].legend(frameon=False, fontsize=8, loc="lower left")
    axes[0].set_title("(a) reward against entropy", fontsize=9.5)
    # (b) policy arrows at lambda = 0.3
    ax = axes[1]
    lam = 0.3
    _, _, pi = soft_value_iteration(mdp, lam)
    dirs = [(0, 0.34), (0.34, 0), (0, -0.34), (-0.34, 0)]
    for (x, y), i in idx.items():
        ax.add_patch(plt.Rectangle((x - 0.5, y - 0.5), 1, 1, fill=False, ec="#999999", lw=0.6))
        if (x, y) in ((3, 3), (3, 2)):
            ax.text(x, y, "G" if y == 3 else "X", ha="center", va="center", fontsize=11, weight="bold", color=GREEN if y == 3 else RED)
            continue
        for a in range(4):
            if pi[i, a] > 0.02:
                ax.arrow(x, y, dirs[a][0] * pi[i, a] * 2, dirs[a][1] * pi[i, a] * 2, head_width=0.07, color=BLUE, length_includes_head=True)
    ax.add_patch(plt.Rectangle((0.5, 0.5), 1, 1, color="#cccccc"))
    ax.set_xlim(-0.55, 3.55); ax.set_ylim(-0.55, 3.55); ax.set_aspect("equal"); ax.axis("off")
    ax.set_title("(b) soft-optimal policy at $\\lambda=%.1f$ (arrow length $\\propto\\pi$)" % lam, fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig35-17", out)


def export_data(out=None):
    """Small reference numbers for the browser demos (private comparison values) and the MDP of the off-policy demo, JSON in ../data."""
    os.makedirs(DATA_OUT, exist_ok=True)
    ref = {}
    eps_list = [1, 10, 25, 50, 100, 200, 300]
    res = maxbias_experiment(runs=4000, episodes=300, estimates=True)
    ref["maxbias"] = {"episodes": eps_list}
    for k in ("q", "dq", "q_est", "dq_est"):
        ref["maxbias"][k] = [float(res[k][e - 1]) for e in eps_list]
    for mode in ("off", "on"):
        A, _ = baird_matrices(0.99, mode)
        ev = np.linalg.eigvals(A)
        h = baird_run(1000, 0.01, mode="expected", behaviour=mode)
        rho = float(np.abs(np.linalg.eigvals(np.eye(8) - 0.01 * A)).max())
        ref["baird_" + mode] = {"min_real_eig": float(ev.real.min()), "w_final": [float(x) for x in h[-1]],
                                "norm_final": float(np.linalg.norm(h[-1])), "spectral_radius": rho}
    P, R, pe, pb = ope_env()
    ref["ope_mismatch_m"] = float((pe ** 2 / pb).sum(1).mean())
    gamma = 0.99
    Qk, Vk = finite_horizon_q(P, R, pe, 41, gamma)
    ref["ope_truth"] = {str(T): float(Vk[T][0]) for T in (1, 10, 20, 40)}

    def Qhat(k):
        return Qk[k] + 0.3 * (1 - gamma ** k) / (1 - gamma) / 3.0, Vk[k] + 0.3 * (1 - gamma ** k) / (1 - gamma) / 3.0
    rng = np.random.default_rng(11)
    reps, n = 400, 100
    ref["ope_rmse"] = {}
    for T in (10, 20):
        errs = {k: [] for k in ("IS", "PDIS", "WIS", "DR")}
        for r in range(reps):
            ss, aa, rr = sample_trajs(P, R, pb, n, T, rng)
            a, b, c, d = ope_estimates(ss, aa, rr, pe, pb, gamma, Qhat, T)
            errs["IS"].append(a.mean() - Vk[T][0]); errs["PDIS"].append(b.mean() - Vk[T][0])
            errs["WIS"].append(c - Vk[T][0]); errs["DR"].append(d.mean() - Vk[T][0])
        ref["ope_rmse"][str(T)] = {k: float(np.sqrt(np.mean(np.square(v)))) for k, v in errs.items()}
    with open(os.path.join(DATA_OUT, "ch35-ope-env.json"), "w") as f:
        json.dump({"P": P.tolist(), "R": R.tolist(), "gamma": gamma, "states": 3, "actions": 2,
                   "note": "random 3-state, 2-action MDP (state-action-next-state transition probabilities P[a][s][s'], mean rewards R[s][a])"}, f)
    cm = chain_mdp(6, 0.9, offset=2.0)
    sd, gn = reinforce_sd_exact(cm, 80, n=30000, seed=5)
    ref["pg_sd"] = sd
    ref["pg_grad_norm"] = gn
    ref["pg_curves"] = {}
    for v in ("none", "const", "state"):
        Js = reinforce_learning_curve(cm, 80, v, iters=150, batch=10, eta=0.05, runs=40, seed=3)
        ref["pg_curves"][v] = {"iters": [25, 50, 100, 150], "mean": [float(Js[:, k].mean()) for k in (25, 50, 100, 150)],
                               "se": [float(Js[:, k].std() / np.sqrt(len(Js))) for k in (25, 50, 100, 150)]}
    ref["pg_Jopt"] = float(objective(cm, greedy(optimal(cm)[0]), np.eye(6)[0]))
    with open(os.path.join(DATA_OUT, "ch35-reference.json"), "w") as f:
        json.dump(ref, f, indent=1)
    print("wrote ch35-reference.json and ch35-ope-env.json")


def fig_export(out=None):
    """Export the JSON reference data."""
    export_data()


FIGURES = {"35.4": fig_35_4, "35.5": fig_35_5, "35.10": fig_35_10, "35.12": fig_35_12, "35.13": fig_35_13,
           "35.14": fig_35_14, "35.15": fig_35_15, "35.16": fig_35_16, "35.17": fig_35_17, "data": fig_export}

if __name__ == "__main__":
    run(FIGURES, CH)
