"""Murphy (2023), Chapter 34: Decision making under uncertainty.

Companion code for Chapter 34 of K. P. Murphy, Probabilistic Machine Learning: Advanced Topics
(MIT Press, 2023; December 2025 draft), pp. 1105-1144, written from scratch with numpy (scipy for the
linear-programming and special functions, scikit-learn for the data sets and base classifiers, PyTorch for
the small dropout network of the active-learning experiment), to be read next to the lecture notes
(../ch34-decision-making.html).

Methods
* 34.1 decision theory: Bayes, minimax and maximum-risk rules for a binomial proportion, the 0-1, squared and
  Hamming losses (MAP, posterior mean, max-marginals), minimum Bayes risk decoding, the three fairness
  criteria and their incompatibility (cube_example, binomial_risks, mbr_decode, Figure 34.2).
* 34.2 influence diagrams: the oil wildcatter, posterior, maximum expected utility and the value of
  information (wildcatter, Figure 34.5).
* 34.3 A/B testing: posterior, optimal sample size, expected reward, regret and error rate
  (ab_nstar, ab_expected_reward, ab_error_rate, ab_regret; Figure 34.6).
* 34.4 bandits: Beta-Bernoulli belief updating (Figure 34.8), UCB (Figure 34.9), Thompson sampling for a
  linear-Gaussian contextual bandit with a normal-inverse-gamma prior (Figure 34.10), regret curves
  against the Lai-Robbins bound and the Bayes-optimal finite-horizon policy by dynamic programming over
  the belief state (own Figures 34.21 and 34.23).
* 34.5-34.6 MDPs: value and action-value functions, Bellman operators, value iteration, policy iteration
  and the two linear programs, on the one-dimensional grid world of Figure 34.13 and on a two-dimensional
  grid world (own Figure 34.22).
* 34.7 active learning: margin, entropy and least-confidence sampling, query by committee, BALD and
  BatchBALD (Figures 34.15 to 34.18 and 34.20; Figure 34.16 with a Gaussian process).

Skipped figures, with reasons: Figure 34.1 (a diagram of the two orders of integration), 34.3 (spectrograms
of recorded speech), 34.4 (influence diagrams), 34.7 (a diagram of the advertising feedback loop), 34.11 and
34.12 (an MDP and a POMDP drawn as graphs), 34.14 (backup diagrams) and 34.19 (an information diagram)
contain nothing computed.

Stand-ins (stated in the captions): Figures 34.17 and 34.20 use the 8 x 8 scikit-learn digits instead of the
28 x 28 MNIST images (a logistic regression and a small dropout network instead of a convolutional
network); Figure 34.18 and 34.15 use a simulated three-class data set. Figure 34.20 is a scaled-down
version (80 queries, 3 repetitions) that finishes in a few minutes on a CPU. Numbers 34.21 to 34.23 are my own
extra figures.
"""
import json
import os
import sys

import numpy as np
from scipy import optimize, special, stats

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 = 34
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")


# ====================================================================== 34.1 decision theory
def cube_example(p1=0.28):
    """The distribution on {0,1}^3 of Figure 34.2: p(1,1,1)=p1, four 'gray' states with mass p2, three with mass 0.

    The gray states are 000 and the three states with a single 1 (so 4 p2 + p1 = 1). Returns the dict of
    probabilities, the MAP state, the max-marginal (MPM) state and their expected Hamming losses."""
    p2 = (1 - p1) / 4
    P = {(1, 1, 1): p1, (0, 0, 0): p2, (1, 0, 0): p2, (0, 1, 0): p2, (0, 0, 1): p2,
         (1, 1, 0): 0.0, (1, 0, 1): 0.0, (0, 1, 1): 0.0}
    states = np.array(list(P.keys()))
    pr = np.array(list(P.values()))
    map_state = tuple(states[np.argmax(pr)])
    marg1 = (pr[:, None] * states).sum(0)                  # P(theta_d = 1)
    mpm = tuple((marg1 > 0.5).astype(int))
    ham = lambda a: float(sum(p * np.sum(np.array(s) != np.array(a)) for s, p in P.items()))
    return dict(P=P, p1=p1, p2=p2, map=map_state, mpm=mpm, marg1=marg1, ham_map=ham(map_state), ham_mpm=ham(mpm), ham=ham)


def binomial_risks(n, p, a, b):
    """Frequentist risk (squared loss) of the Bayes estimator (x+a)/(n+a+b) of a binomial proportion, vectorised in p."""
    p = np.asarray(p, float)
    c = n + a + b
    return (n * p * (1 - p) + (a - (a + b) * p) ** 2) / c ** 2


def minimax_binomial(n):
    """The minimax estimator of a binomial proportion under squared loss: Bayes under Beta(sqrt(n)/2, sqrt(n)/2).

    Its risk is constant, n / (4 (n + sqrt n)^2)."""
    a = np.sqrt(n) / 2
    return a, n / (4 * (n + np.sqrt(n)) ** 2)


def mbr_decode(candidates, samples, loss):
    """Empirical minimum-Bayes-risk decoding: the candidate with the smallest average loss against the samples."""
    risks = np.array([np.mean([loss(y, c) for y in samples]) for c in candidates])
    return int(np.argmin(risks)), risks


def fig_34_2(out=None):
    """Figure 34.2: a distribution on {0,1}^3 whose mode is untypical; MAP versus max-marginals (MPM)."""
    ex = cube_example(0.28)
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.5), gridspec_kw=dict(width_ratios=[1.25, 1]))
    ax = axes[0]
    # oblique projection of the cube
    def pos(s):
        x, y, z = s
        return (x + 0.55 * y, z + 0.45 * y)
    for s in ex["P"]:
        for d in range(3):
            t = list(s)
            if t[d] == 0:
                t[d] = 1
                x0, y0 = pos(s); x1, y1 = pos(t)
                ax.plot([x0, x1], [y0, y1], color="#bbbbbb", lw=1.1, zorder=1)
    for s, p in ex["P"].items():
        x, y = pos(s)
        if s == ex["map"]:
            ax.scatter(x, y, s=330, color="black", zorder=3)
            ax.annotate("MAP, $p_1$=%.2f" % p, (x, y), xytext=(x - 0.55, y + 0.22), fontsize=8.5)
        elif p > 0:
            ax.scatter(x, y, s=330, color="#9a9a9a", zorder=3)
        else:
            ax.scatter(x, y, s=330, facecolor="white", edgecolor="black", zorder=3)
        ax.text(x, y - 0.17, "".join(map(str, s)), ha="center", va="top", fontsize=7.5)
    x, y = pos(ex["mpm"])
    ax.scatter(x, y, s=720, facecolor="none", edgecolor=RED, lw=2.2, zorder=4)
    ax.annotate("MPM $(0,0,0)$", (x, y), xytext=(x - 0.3, y - 0.42), color=RED, fontsize=9)
    ax.text(1.15, -0.72, "gray: $p_2$=%.2f\nwhite: probability 0" % ex["p2"], fontsize=8.5)
    ax.set_xlim(-0.5, 2.0); ax.set_ylim(-0.95, 1.75); ax.axis("off")
    ax.set_title("Cube $\\{0,1\\}^3$, edges join Hamming neighbours")
    ax = axes[1]
    pgrid = np.linspace(0.2005, 0.5, 100)
    h_map, h_mpm = [], []
    for p1 in pgrid:
        e = cube_example(p1)
        h_map.append(e["ham_map"]); h_mpm.append(e["ham_mpm"])
    ax.plot(pgrid, h_map, color="black", label="MAP $(1,1,1)$ or other mode")
    ax.plot(pgrid, h_mpm, color=RED, label="max-marginals (MPM)")
    ax.axvline(1 / 3, color=GREY, ls=":"); ax.text(0.34, 1.7, "$2p_2=p_1$", ha="left", fontsize=8, color=GREY)
    ax.set_xlabel("$p_1$ (mass of the isolated mode, $p_1>p_2$)"); ax.set_ylabel("expected Hamming loss")
    ax.set_title("MPM wins while $2p_2>p_1$"); ax.legend(fontsize=7.5, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig34-2", out)


# ====================================================================== 34.2 oil wildcatter
PRIOR_O = np.array([0.5, 0.3, 0.2])
UTIL = np.array([[0.0, 0.0, 0.0], [-70.0, 50.0, 200.0]])        # U[d, o], d = 0 do not drill, 1 drill
SOUND = np.array([[0.6, 0.3, 0.1], [0.3, 0.4, 0.3], [0.1, 0.4, 0.5]])   # p(s | o), rows o


def wildcatter():
    """All the numbers of Section 34.2: EU without data, posteriors, EU(d|s), MEU with the sounding, EVSI and EVPI."""
    eu0 = UTIL @ PRIOR_O
    ps = PRIOR_O @ SOUND
    post = (PRIOR_O[:, None] * SOUND) / ps                         # p(o | s), column s
    eu_s = UTIL @ post                                             # [d, s]
    best = eu_s.max(0)
    meu = float(ps @ best)
    evpi = float(PRIOR_O @ UTIL.max(0) - eu0.max())
    return dict(eu0=eu0, meu0=float(eu0.max()), ps=ps, post=post, eu_s=eu_s, policy=eu_s.argmax(0), best=best,
                meu=meu, evsi=meu - float(eu0.max()), evpi=evpi)


def fig_34_5(out=None):
    """Figure 34.5: the decision tree of the oil wildcatter (computed from the model)."""
    w = wildcatter()
    fig, ax = plt.subplots(figsize=(6.4, 3.9))
    ax.set_xlim(0, 10); ax.set_ylim(0, 10); ax.axis("off")
    order = [1, 0, 2]                                   # s = 1, 0, 2 top to bottom as in the book
    ys = {1: 8.2, 0: 5.0, 2: 1.8}
    ax.scatter([0.6], [5.0], s=180, color="black", zorder=3)
    for s in order:
        y = ys[s]
        ax.plot([0.6, 3.2], [5.0, y], color="black", lw=1)
        ax.scatter([3.2], [y], s=150, color="black", zorder=3)
        ax.text(1.55, (5.0 + y) / 2 + 0.35, "$S=%d$\n$p=%.2f$" % (s, w["ps"][s]), fontsize=8.5, ha="center")
        for k, (lab, d) in enumerate([("Drill", 1), ("Don't drill", 0)]):
            y2 = y + (0.9 if k == 0 else -0.9)
            ax.plot([3.2, 5.6], [y, y2], color="black", lw=1)
            ax.scatter([5.6], [y2], marker="s", s=80, color="black", zorder=3)
            v = w["eu_s"][d, s]
            ax.text(3.7, (y + y2) / 2 + (0.28 if k == 0 else -0.55), lab, fontsize=8)
            ax.plot([5.6, 6.8], [y2, y2], color="black", lw=1)
            good = v >= w["best"][s] - 1e-9
            ax.scatter([7.0], [y2], marker="D", s=150, color=GREEN if good else RED, zorder=3)
            ax.text(7.4, y2, "%.1f" % v, va="center", fontsize=9)
    ax.text(0.6, 9.6, "MEU = %.1f" % w["meu"], fontsize=9.5, weight="bold")
    ax.text(5.6, 9.6, "green: optimal action", fontsize=8, color=GREEN)
    savefig(fig, CH, "fig34-5", out)


# ====================================================================== 34.3 A/B testing
def ab_stats(N, m, tau, sigma, n):
    s = np.sqrt(tau ** 2 + sigma ** 2 / n)
    return s


def ab_expected_reward(n, N, m, tau, sigma):
    """Total expected reward (34.42) of a symmetric test with n per arm: N m + (N - 2n) tau^2 / (sqrt(pi) sqrt(tau^2 + sigma^2/n))."""
    n = np.asarray(n, float)
    return N * m + (N - 2 * n) * tau ** 2 / (np.sqrt(np.pi) * np.sqrt(tau ** 2 + sigma ** 2 / n))


def ab_general_reward(n0, n1, N, m0, m1, tau0, tau1, sigma0, sigma1):
    """Expected total reward (34.36) + (34.39) for unequal arms."""
    e = m0 - m1
    v = np.sqrt(tau1 ** 4 / (tau1 ** 2 + sigma1 ** 2 / n1) + tau0 ** 4 / (tau0 ** 2 + sigma0 ** 2 / n0))
    roll = (N - n0 - n1) * (m1 + e * stats.norm.cdf(e / v) + v * stats.norm.pdf(e / v))
    return n0 * m0 + n1 * m1 + roll


def ab_nstar(N, tau, sigma):
    """Optimal test size per arm (34.43): sqrt(N u^2/4 + (3 u^2/4)^2) - 3 u^2/4, u = sigma/tau."""
    u2 = (sigma / tau) ** 2
    return float(np.sqrt(N * u2 / 4 + (0.75 * u2) ** 2) - 0.75 * u2)


def ab_error_rate(n, tau, sigma):
    """Probability of deploying the worse arm, averaged over the prior: 1/2 - arctan(tau sqrt(n) / sigma) / pi.

    (The book's (34.47) is the joint probability P(pi=1, mu1<mu0), which is half of this.)"""
    n = np.asarray(n, float)
    return 0.5 - np.arctan(tau * np.sqrt(n) / sigma) / np.pi


def ab_regret(n, N, tau, sigma):
    """Regret (34.45) against the oracle that knows which arm is better."""
    s = np.sqrt(tau ** 2 + sigma ** 2 / n)
    return N * tau / np.sqrt(np.pi) * (1 - tau / s) + 2 * n * tau ** 2 / (np.sqrt(np.pi) * s)


def ab_book_example():
    N, m, tau = 100_000, 0.68, 0.03
    sigma = np.sqrt(m * (1 - m))
    ns = ab_nstar(N, tau, sigma)
    n_int = int(round(ns))
    r_test = 2 * n_int * m
    total = float(ab_expected_reward(n_int, N, m, tau, sigma))
    return dict(N=N, m=m, tau=tau, sigma=float(sigma), nstar=ns, n=n_int, r_test=r_test, r_roll=total - r_test,
                total=total, err=float(ab_error_rate(n_int, tau, sigma)), regret=float(ab_regret(ns, N, tau, sigma)),
                eff=2 * tau / np.sqrt(np.pi))


def simulate_ab(n, N, m, tau, sigma, reps=200_000, seed=0):
    """Monte Carlo: draw mu_j ~ N(m, tau^2), observe n samples per arm (their means), deploy the arm with larger mean.

    Returns the mean total reward and the error rate."""
    rng = np.random.default_rng(seed)
    mu = m + tau * rng.standard_normal((reps, 2))
    ybar = mu + sigma / np.sqrt(n) * rng.standard_normal((reps, 2))
    pick = np.argmax(ybar, axis=1)
    reward = n * mu.sum(1) + (N - 2 * n) * mu[np.arange(reps), pick]
    err = np.mean(pick != np.argmax(mu, axis=1))
    return reward.mean(), reward.std() / np.sqrt(reps), err


def fig_34_6(out=None):
    """Figure 34.6: total expected conversions and error rate against the test size (website example)."""
    ex = ab_book_example()
    nn = np.arange(20, 50001, 20)
    R = ab_expected_reward(nn, ex["N"], ex["m"], ex["tau"], ex["sigma"])
    E = ab_error_rate(nn, ex["tau"], ex["sigma"])
    fig, axes = plt.subplots(1, 2, figsize=(8.2, 3.1))
    ax = axes[0]
    ax.plot(nn, R, color=BLUE)
    ax.axvline(ex["nstar"], color=RED, ls="--", lw=1)
    ax.text(ex["nstar"] + 800, R.min() + 0.08 * (R.max() - R.min()), "$n^*=%.1f$" % ex["nstar"], color=RED, fontsize=9)
    ax.set_xlim(0, 40000); ax.set_xticks([0, 10000, 20000, 30000, 40000])
    ax.set_xlabel("test size $n$ per arm"); ax.set_ylabel("expected number of conversions")
    ax.set_ylim(68000, 69800)
    axes[0].set_title("(a) total expected reward")
    ax = axes[1]
    ax.plot(nn, E, color=BLUE)
    ax.axvline(ex["nstar"], color=RED, ls="--", lw=1)
    ax.set_xlabel("test size $n$ per arm"); ax.set_ylabel("expected error rate"); ax.set_ylim(0, 0.52)
    ax.set_title("(b) probability of deploying the worse arm")
    fig.tight_layout()
    savefig(fig, CH, "fig34-6", out)


# ====================================================================== 34.4 bandits
def beta_update(a, b, success):
    return (a + 1, b) if success else (a, b + 1)


def fig_34_8(out=None):
    """Figure 34.8: sequential belief updating for a two-armed beta-Bernoulli bandit."""
    xs = np.linspace(0.001, 0.999, 400)
    priors = [(1, 1), (2, 2)]
    steps = [(0, 1), (1, 1), (0, 0), (1, 0), (0, 1)]       # (arm, success)
    ab = [list(p) for p in priors]
    states = [[tuple(p) for p in ab]]
    labels = ["prior"]
    for arm, ok in steps:
        ab[arm] = list(beta_update(ab[arm][0], ab[arm][1], ok))
        states.append([tuple(p) for p in ab])
        labels.append("pull arm %d: %s" % (arm + 1, "success" if ok else "failure"))
    fig, axes = plt.subplots(2, 3, figsize=(8.4, 4.6), sharex=True)
    for k, ax in enumerate(axes.ravel()):
        for arm, col in enumerate([BLUE, ORANGE]):
            a, b = states[k][arm]
            ax.plot(xs, stats.beta.pdf(xs, a, b), color=col, label="arm %d: Beta(%d,%d)" % (arm + 1, a, b))
        ax.set_title("t=%d, %s" % (k, labels[k]), fontsize=8.5)
        ax.legend(fontsize=7, loc="upper center")
        ax.set_ylim(0, 4.6)
        if k >= 3:
            ax.set_xlabel("$\\mu_a$")
    fig.tight_layout()
    savefig(fig, CH, "fig34-8", out)


def fig_34_9(out=None):
    """Figure 34.9: posterior reward distributions of three Gaussian arms and their upper confidence bounds."""
    mu = np.array([0.0, 0.6, 1.3]); sd = np.array([1.0, 0.45, 0.25]); c = 2.0
    xs = np.linspace(-3.5, 3.5, 500)
    fig, ax = plt.subplots(figsize=(5.8, 3.3))
    cols = [BLUE, ORANGE, GREEN]
    for a in range(3):
        ax.plot(xs, stats.norm.pdf(xs, mu[a], sd[a]), color=cols[a], label="arm %d: $Q$=%.1f, $\\sigma$=%.2f" % (a + 1, mu[a], sd[a]))
        top = stats.norm.pdf(mu[a], mu[a], sd[a])
        ax.plot([mu[a], mu[a]], [0, top], color=cols[a], ls=":")
        yb = top * 0.45 + 0.02 * a
        ax.plot([mu[a] - c * sd[a], mu[a] + c * sd[a]], [yb, yb], color=cols[a], lw=2.2)
        ax.scatter([mu[a] + c * sd[a]], [yb], marker="|", s=160, color=cols[a], zorder=3)
        ax.text(mu[a] + c * sd[a] + 0.07, yb, "UCB %.2f" % (mu[a] + c * sd[a]), fontsize=8, va="center", color=cols[a])
    ax.set_xlabel("expected reward"); ax.set_ylabel("posterior density")
    ax.set_title("Greedy picks arm 3 (largest mean); UCB with $c=2$ picks arm 1 (largest bound)", fontsize=8.5)
    ax.legend(fontsize=8, loc="upper left")
    savefig(fig, CH, "fig34-9", out)


def nig_update(mu0, Lam0, a0, b0, Phi, y):
    """Normal-inverse-gamma update for Bayesian linear regression (completing the square)."""
    Lam = Lam0 + Phi.T @ Phi
    mu = np.linalg.solve(Lam, Lam0 @ mu0 + Phi.T @ y)
    a = a0 + len(y) / 2
    b = b0 + 0.5 * (y @ y + mu0 @ Lam0 @ mu0 - mu @ Lam @ mu)
    return mu, Lam, a, b


def thompson_linear(T=300, seed=0, horizon=4.0):
    """Thompson sampling for the three-arm contextual bandit of Figure 34.10 (context (1, t, t^2), sigma = 1).

    Each arm has its own conjugate normal-inverse-gamma prior (mu0 = 0, Lambda0 = I, a0 = b0 = 1)."""
    rng = np.random.default_rng(seed)
    W = np.array([[-5.0, 2.0, 0.5], [0.0, 0.0, 0.0], [5.0, -1.5, -1.0]])
    ts = np.linspace(0, horizon, T)
    S = np.stack([np.ones(T), ts, ts ** 2], 1)
    K = 3
    Lam = [np.eye(3) for _ in range(K)]; mu = [np.zeros(3) for _ in range(K)]; a_ = [1.0] * K; b_ = [1.0] * K
    XtX = [np.zeros((3, 3)) for _ in range(K)]; Xty = [np.zeros(3) for _ in range(K)]; yty = [0.0] * K; cnt = [0] * K
    acts = np.zeros(T, int); rew = np.zeros(T); reg = np.zeros(T)
    for t in range(T):
        s = S[t]
        scores = np.zeros(K)
        for k in range(K):
            sig2 = 1.0 / rng.gamma(a_[k], 1.0 / b_[k])
            w = rng.multivariate_normal(mu[k], sig2 * np.linalg.inv(Lam[k]))
            scores[k] = w @ s
        k = int(np.argmax(scores))
        r = W[k] @ s + rng.standard_normal()
        acts[t] = k; rew[t] = r
        reg[t] = (W @ s).max() - W[k] @ s
        XtX[k] += np.outer(s, s); Xty[k] += s * r; yty[k] += r * r; cnt[k] += 1
        Lam[k] = np.eye(3) + XtX[k]
        mu[k] = np.linalg.solve(Lam[k], Xty[k])
        a_[k] = 1.0 + cnt[k] / 2
        b_[k] = 1.0 + 0.5 * (yty[k] - mu[k] @ Lam[k] @ mu[k])
    return dict(ts=ts, S=S, W=W, acts=acts, rew=rew, reg=reg)


def fig_34_10(out=None):
    """Figure 34.10: Thompson sampling on a linear-Gaussian contextual bandit, context (1, t, t^2)."""
    res = thompson_linear(300, 0)
    ts, W, S = res["ts"], res["W"], res["S"]
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.0))
    cols = [BLUE, GREY, RED]
    ax = axes[0]
    for k in range(3):
        ax.plot(ts, S @ W[k], color=cols[k], label="arm %d" % k)
    ax.set_xlabel("time"); ax.set_title("(a) true reward of each arm"); ax.legend(fontsize=8)
    ax = axes[1]
    for k in range(3):
        cum = np.cumsum(np.where(res["acts"] == k, res["rew"], 0.0))
        ax.plot(ts, cum, color=cols[k], label="arm %d" % k)
    ax.set_xlabel("time"); ax.set_ylabel("cumulative reward"); ax.set_title("(b) cumulative reward per arm"); ax.legend(fontsize=8)
    ax = axes[2]
    regs = np.array([np.cumsum(thompson_linear(300, s)["reg"]) for s in range(1, 11)])
    ax.plot(ts, np.cumsum(res["reg"]), color=BLUE, label="observed (one run)")
    ax.plot(ts, regs.mean(0), color=GREEN, label="mean of 10 other runs")
    T = len(ts); c = np.cumsum(res["reg"])[-1] / np.sqrt(T)
    ax.plot(ts, c * np.sqrt(np.arange(1, T + 1)), color=RED, ls="--", label="$c\\sqrt{t}$")
    ax.set_xlabel("time"); ax.set_ylabel("cumulative regret"); ax.set_title("(c) cumulative regret"); ax.legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig34-10", out)


# Bernoulli bandit simulation, vectorised over runs
def simulate_bandit(algo, mu, T, R, seed=0, c=2.0, eps=0.1, prior=(1.0, 1.0)):
    """Mean cumulative pseudo-regret (and its standard error) over R runs of a K-armed Bernoulli bandit.

    algo in {'greedy', 'eps', 'ucb1', 'bayesucb' (posterior mean + c posterior sd), 'ts'}; the same reward table is used by every algorithm
    (common random numbers) because the seed fixes it."""
    mu = np.asarray(mu, float)
    K = len(mu)
    best = mu.max()
    rng_r = np.random.default_rng(seed)
    U = rng_r.random((R, T, K))
    rng = np.random.default_rng(seed + 1000)
    n = np.zeros((R, K)); s = np.zeros((R, K))
    reg = np.zeros((R, T))
    ar = np.arange(R)
    for t in range(T):
        if t < K:
            a = np.full(R, t)
        elif algo == "greedy":
            a = np.argmax(s / n + 1e-9 * rng.random((R, K)), 1)
        elif algo == "eps":
            a = np.argmax(s / n + 1e-9 * rng.random((R, K)), 1)
            rnd = rng.random(R) < eps
            a = np.where(rnd, rng.integers(0, K, R), a)
        elif algo == "ucb1":
            a = np.argmax(s / n + np.sqrt(2 * np.log(t + 1) / n), 1)
        elif algo == "bayesucb":
            al, be = prior[0] + s, prior[1] + n - s                 # Beta posterior: mean and exact standard deviation
            a = np.argmax(al / (al + be) + c * np.sqrt(al * be / ((al + be) ** 2 * (al + be + 1))), 1)
        elif algo == "ts":
            a = np.argmax(rng.beta(prior[0] + s, prior[1] + n - s), 1)
        else:
            raise ValueError(algo)
        r = (U[ar, t, a] < mu[a]).astype(float)
        n[ar, a] += 1; s[ar, a] += r
        reg[:, t] = best - mu[a]
    cum = np.cumsum(reg, 1)
    return cum.mean(0), cum.std(0) / np.sqrt(R)


def lai_robbins_const(mu):
    """sum_{a: Delta_a > 0} Delta_a / KL(Ber(mu_a) || Ber(mu*)): the slope of the lower bound (34.73) against log T."""
    mu = np.asarray(mu, float); best = mu.max()
    kl = lambda p, q: p * np.log(p / q) + (1 - p) * np.log((1 - p) / (1 - q))
    return float(sum((best - m) / kl(m, best) for m in mu if m < best))


def fig_34_21(out=None):
    """Own Figure 34.21: cumulative regret of greedy, epsilon-greedy, UCB1, a Bayesian UCB and Thompson sampling."""
    mu = [0.5, 0.45, 0.4, 0.3]
    T, R = 3000, 300
    fig, axes = plt.subplots(1, 2, figsize=(9.2, 3.3))
    names = [("greedy", "greedy", GREY), ("eps", "$\\varepsilon$-greedy, $\\varepsilon=0.1$", ORANGE), ("ucb1", "UCB1", BLUE),
             ("bayesucb", "Bayes UCB, $c=2$", PURPLE), ("ts", "Thompson", RED)]
    curves = {}
    for key, lab, col in names:
        m_, se = simulate_bandit(key, mu, T, R, seed=3)
        curves[key] = m_
        axes[0].plot(np.arange(1, T + 1), m_, color=col, label=lab)
        axes[1].plot(np.arange(1, T + 1), m_, color=col, label=lab)
    tt = np.arange(1, T + 1)
    lr = lai_robbins_const(mu)
    t0 = 100
    axes[1].plot(tt[t0:], curves["ts"][t0] + lr * np.log(tt[t0:] / tt[t0]), color="black", ls="--", label="slope $C$ of the Lai-Robbins bound")
    axes[0].set_xlabel("$t$"); axes[0].set_ylabel("cumulative regret"); axes[0].set_title("(a) linear scale")
    axes[1].set_xscale("log"); axes[1].set_xlabel("$t$ (log scale)"); axes[1].set_title("(b) the same on a log time axis")
    axes[0].legend(fontsize=7.5)
    fig.tight_layout()
    savefig(fig, CH, "fig34-21", out)


def bayes_optimal_two_arm(T, a0=(1, 1), b0=(1, 1)):
    """Bayes-optimal expected total reward of a two-armed Bernoulli bandit with independent Beta priors, horizon T.

    Dynamic programming over the belief state (s1, f1, s2, f2); V_t depends only on the counts. Returns V_0."""
    # V[t] is an array over (s1, f1, s2) with f2 = t - s1 - f1 - s2; use dictionaries of arrays indexed [s1][f1][s2]
    A1, B1 = a0[0], b0[0]
    A2, B2 = a0[1], b0[1]
    # work with total pulls t = s1+f1+s2+f2 from T down to 0; represent V_t as a dense array (t+1)^3
    V = np.zeros((T + 1, T + 1, T + 1))    # t = T: no future reward
    for t in range(T - 1, -1, -1):
        Vn = V                                   # shape (t+2)^3 indexed by (s1, f1, s2)
        W = np.zeros((t + 1, t + 1, t + 1))
        s1, f1, s2 = np.meshgrid(np.arange(t + 1), np.arange(t + 1), np.arange(t + 1), indexing="ij")
        f2 = t - s1 - f1 - s2
        valid = f2 >= 0
        s1v, f1v, s2v, f2v = s1[valid], f1[valid], s2[valid], f2[valid]
        p1 = (A1 + s1v) / (A1 + B1 + s1v + f1v)
        p2 = (A2 + s2v) / (A2 + B2 + s2v + f2v)
        # pull arm 1: success -> (s1+1, f1, s2), failure -> (s1, f1+1, s2); arm 2: success (s1,f1,s2+1), failure (s1,f1,s2)
        q1 = p1 * (1 + Vn[s1v + 1, f1v, s2v]) + (1 - p1) * Vn[s1v, f1v + 1, s2v]
        q2 = p2 * (1 + Vn[s1v, f1v, s2v + 1]) + (1 - p2) * Vn[s1v, f1v, s2v]
        W[valid] = np.maximum(q1, q2)
        V = W
    return float(V[0, 0, 0])


def bayes_policy_value(policy, T, a0=(1, 1), b0=(1, 1), R=4000, seed=0):
    """Monte Carlo Bayesian expected total reward of a policy when mu_a ~ Beta(a0[a], b0[a]) (the mean over the prior)."""
    rng = np.random.default_rng(seed)
    mu = np.stack([rng.beta(a0[0], b0[0], R), rng.beta(a0[1], b0[1], R)], 1)
    n = np.zeros((R, 2)); s = np.zeros((R, 2)); tot = np.zeros(R); ar = np.arange(R)
    for t in range(T):
        if policy == "ts":
            a = np.argmax(rng.beta(np.array(a0) + s, np.array(b0) + n - s), 1)
        elif policy == "greedy":
            m_ = (np.array(a0) + s) / (np.array(a0) + np.array(b0) + n)
            a = np.argmax(m_ + 1e-9 * rng.random((R, 2)), 1)
        elif policy == "ucb1":
            a = np.where(n.min(1) == 0, np.argmin(n, 1), np.argmax(s / np.maximum(n, 1) + np.sqrt(2 * np.log(t + 1) / np.maximum(n, 1)), 1))
        r = (rng.random(R) < mu[ar, a]).astype(float)
        n[ar, a] += 1; s[ar, a] += r; tot += r
    return tot.mean(), tot.std() / np.sqrt(R)


def fig_34_23(out=None):
    """Own Figure 34.23: the Bayes-optimal policy (dynamic programming on the belief state) against UCB1, Thompson and greedy."""
    Ts = [2, 5, 10, 15, 20, 25, 30, 40]
    opt = [bayes_optimal_two_arm(T) for T in Ts]
    fig, ax = plt.subplots(figsize=(5.4, 3.2))
    ax.plot(Ts, [o - T / 2 for T, o in zip(Ts, opt)], "o-", color="black", label="Bayes optimal (DP on belief state)")
    for pol, col, lab in [("ts", RED, "Thompson"), ("greedy", GREY, "greedy on posterior mean"), ("ucb1", BLUE, "UCB1")]:
        vals = [bayes_policy_value(pol, T, R=6000, seed=2)[0] for T in Ts]
        ax.plot(Ts, [v - T / 2 for T, v in zip(Ts, vals)], "s--", ms=3.5, color=col, label=lab)
    ax.set_xlabel("horizon $T$"); ax.set_ylabel("expected reward minus $T/2$")
    ax.set_title("Two Bernoulli arms, uniform priors", fontsize=9)
    ax.legend(fontsize=7.5)
    savefig(fig, CH, "fig34-23", out)


# ====================================================================== 34.5-34.6 MDPs
def evaluate_policy(P, R, gamma, pi):
    """v = (I - gamma T_pi)^{-1} r_pi for a deterministic policy pi (array of actions); P[a, s, s'], R[s, a]."""
    S = R.shape[0]
    T = P[pi, np.arange(S), :]
    r = R[np.arange(S), pi]
    return np.linalg.solve(np.eye(S) - gamma * T, r)


def q_from_v(P, R, gamma, v):
    return R + gamma * np.einsum("ast,t->sa", P, v)


def value_iteration(P, R, gamma, tol=1e-10, max_iter=100000):
    """Value iteration (34.86); returns V, the greedy policy, the iteration count and the sup-norm errors history."""
    S = R.shape[0]
    v = np.zeros(S); hist = []
    for k in range(max_iter):
        vn = q_from_v(P, R, gamma, v).max(1)
        hist.append(np.abs(vn - v).max())
        v = vn
        if hist[-1] < tol:
            break
    return v, q_from_v(P, R, gamma, v).argmax(1), k + 1, np.array(hist)


def policy_iteration(P, R, gamma, pi0=None):
    S, A = R.shape
    pi = np.zeros(S, int) if pi0 is None else pi0.copy()
    vs = []
    for it in range(1000):
        v = evaluate_policy(P, R, gamma, pi)
        vs.append(v)
        pin = q_from_v(P, R, gamma, v).argmax(1)
        # keep the old action if it is tied with the greedy one, so that the loop terminates
        q = q_from_v(P, R, gamma, v)
        keep = np.isclose(q[np.arange(S), pi], q.max(1), atol=1e-12, rtol=0)
        pin = np.where(keep, pi, pin)
        if np.array_equal(pin, pi):
            return v, pi, it + 1, vs
        pi = pin
    raise RuntimeError("policy iteration did not converge")


def lp_primal(P, R, gamma, p0):
    """The primal LP (34.92): min p0.V s.t. V(s) >= R(s,a) + gamma sum_s' p(s'|s,a) V(s')."""
    S, A = R.shape
    A_ub, b_ub = [], []
    for s in range(S):
        for a in range(A):
            row = gamma * P[a, s, :].copy(); row[s] -= 1.0
            A_ub.append(row); b_ub.append(-R[s, a])
    res = optimize.linprog(p0, A_ub=np.array(A_ub), b_ub=np.array(b_ub), bounds=[(None, None)] * S, method="highs")
    return res.x, res.fun


def lp_dual(P, R, gamma, p0):
    """The dual LP (34.93): max sum d(s,a) R(s,a) over occupancy measures d >= 0."""
    S, A = R.shape
    Aeq = np.zeros((S, S * A)); beq = (1 - gamma) * p0
    for s in range(S):
        for a in range(A):
            Aeq[s, s * A + a] += 1.0
    for sp in range(S):
        for s in range(S):
            for a in range(A):
                Aeq[sp, s * A + a] -= gamma * P[a, s, sp]
    res = optimize.linprog(-R.reshape(-1), A_eq=Aeq, b_eq=beq, bounds=[(0, None)] * (S * A), method="highs")
    return res.x.reshape(S, A), -res.fun


def chain_mdp(n_inner=3):
    """The 1-d grid world of Figure 34.13: ST1, s1..s3, ST2 with deterministic moves (action 0 = up, 1 = down).

    The reward is 1 for entering ST2; both end states are absorbing with zero reward afterwards."""
    S = n_inner + 2
    P = np.zeros((2, S, S)); R = np.zeros((S, 2))
    for s in range(S):
        if s in (0, S - 1):
            P[:, s, s] = 1.0
        else:
            P[0, s, s - 1] = 1.0; P[1, s, s + 1] = 1.0
    R[S - 2, 1] = 1.0
    return P, R


def fig_34_13(out=None):
    """Figure 34.13: optimal Q-functions of the one-dimensional grid world for gamma = 0, 1 and 0.9."""
    P, R = chain_mdp(3)
    fig, axes = plt.subplots(1, 3, figsize=(7.8, 2.9))
    for ax, g in zip(axes, [0.0, 1.0, 0.9]):
        v, pol, it, _ = value_iteration(P, R, g, tol=1e-12, max_iter=200)
        Q = q_from_v(P, R, g, v)[1:4]
        im = ax.imshow(Q, cmap="Blues", vmin=0, vmax=1.15, aspect="auto")
        for i in range(3):
            for j in range(2):
                ax.text(j, i, "%.2f" % Q[i, j] if abs(Q[i, j] - round(Q[i, j], 1)) > 1e-9 else "%.1f" % Q[i, j], ha="center", va="center", fontsize=10)
        ax.set_xticks([0, 1]); ax.set_xticklabels(["up", "down"]); ax.set_yticks([0, 1, 2]); ax.set_yticklabels(["$s_1$", "$s_2$", "$s_3$"])
        ax.set_title("$\\gamma=%g$" % g, fontsize=10)
    fig.suptitle("Optimal action values $Q_*(s,a)$ (the goal $S_{T2}$ lies below $s_3$)", fontsize=9, y=1.0)
    fig.tight_layout()
    savefig(fig, CH, "fig34-13", out)


GRID_LAYOUT = ["....",
               ".#.G",
               "....",
               "S..X"]                                     # a 4 x 4 grid world: wall, goal G (+1), pit X (-1)


def grid_mdp(layout=GRID_LAYOUT, slip=0.2, step=-0.04, goal_r=1.0, pit_r=-1.0):
    """A grid world MDP: actions up, right, down, left; with probability slip the agent moves at right angles.

    G and X are absorbing; walls block movement. The reward is received on entering a state."""
    H, W = len(layout), len(layout[0])
    cells = [(i, j) for i in range(H) for j in range(W) if layout[i][j] != "#"]
    idx = {c: k for k, c in enumerate(cells)}
    S = len(cells)
    moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    P = np.zeros((4, S, S)); R = np.zeros((S, 4))
    for (i, j), s in idx.items():
        ch = layout[i][j]
        if ch in "GX":
            P[:, s, s] = 1.0
            continue
        for a in range(4):
            for da, pr in [(0, 1 - slip), (1, slip / 2), (3, slip / 2)]:
                di, dj = moves[(a + da) % 4]
                ni, nj = i + di, j + dj
                if not (0 <= ni < H and 0 <= nj < W) or layout[ni][nj] == "#":
                    ni, nj = i, j
                s2 = idx[(ni, nj)]
                P[a, s, s2] += pr
                c2 = layout[ni][nj]
                R[s, a] += pr * (goal_r if c2 == "G" else pit_r if c2 == "X" else step)
    return P, R, cells, idx


def fig_34_22(out=None):
    """Own Figure 34.22: value iteration on a stochastic grid world: contraction at rate gamma, V* and the greedy policy."""
    P, R, cells, idx = grid_mdp()
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.3), gridspec_kw=dict(width_ratios=[1.0, 1.0]))
    ax = axes[0]
    v_star = None
    for g, col in [(0.5, GREEN), (0.9, BLUE), (0.99, RED)]:
        v, pol, it, hist = value_iteration(P, R, g, tol=1e-13)
        # error against V* and the bound gamma^k * ||V_0 - V*||
        vk = np.zeros(len(v)); errs = []
        for k in range(min(it, 400)):
            errs.append(np.abs(vk - v).max())
            vk = q_from_v(P, R, g, vk).max(1)
        errs = np.array(errs)
        ax.semilogy(errs, color=col, label="$\\gamma=%g$" % g)
        ax.semilogy(errs[0] * g ** np.arange(len(errs)), color=col, ls=":", lw=1)
    ax.set_ylim(1e-12, 5)
    ax.set_xlabel("iteration $k$"); ax.set_ylabel("$\\|V_k-V_*\\|_\\infty$ (dotted: $\\gamma^k\\|V_0-V_*\\|_\\infty$)", fontsize=8.5)
    ax.legend(fontsize=8); ax.set_title("(a) value iteration is a contraction", fontsize=9.5)
    ax = axes[1]
    v, pol, it, _ = value_iteration(P, R, 0.9, tol=1e-12)
    H, W = len(GRID_LAYOUT), len(GRID_LAYOUT[0])
    grid = np.full((H, W), np.nan)
    for (i, j), s in idx.items():
        grid[i, j] = v[s]
    ax.imshow(grid, cmap="RdYlGn", vmin=-1, vmax=1)
    arrows = ["^", ">", "v", "<"]
    for (i, j), s in idx.items():
        ch = GRID_LAYOUT[i][j]
        if ch in "GX":
            ax.text(j, i, ch + "\n%.2f" % v[s], ha="center", va="center", fontsize=8)
        else:
            ax.text(j, i + 0.18, "%.2f" % v[s], ha="center", va="center", fontsize=7.5)
            ax.text(j, i - 0.18, arrows[pol[s]], ha="center", va="center", fontsize=13, color="black")
    for i in range(H):
        for j in range(W):
            if GRID_LAYOUT[i][j] == "#":
                ax.add_patch(plt.Rectangle((j - .5, i - .5), 1, 1, color="#444444"))
    ax.set_xticks([]); ax.set_yticks([])
    ax.set_title("(b) $V_*$ and greedy policy, $\\gamma=0.9$", fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig34-22", out)


# ====================================================================== 34.7 active learning
def entropy(p, axis=-1):
    p = np.clip(p, 1e-12, 1)
    return -(p * np.log(p)).sum(axis)


def margin_score(p):
    """Uncertainty by the margin, in the book's sign: p2 - p1 (larger = more uncertain)."""
    ps = np.sort(p, axis=-1)
    return ps[..., -2] - ps[..., -1]


def least_conf(p):
    return 1 - p.max(-1)


def make_toy3(n=300, seed=0):
    from sklearn.datasets import make_classification
    X, y = make_classification(n_samples=n, n_features=2, n_informative=2, n_redundant=0, n_classes=3,
                               n_clusters_per_class=1, class_sep=1.2, random_state=seed)
    return X, y


def fit_lr(X, y):
    from sklearn.linear_model import LogisticRegression
    return LogisticRegression(C=10.0, max_iter=2000).fit(X, y)


def fig_34_15(out=None):
    """Figure 34.15: decision boundaries of a logistic regression with random versus margin-sampled extra labels."""
    X, y = make_toy3(400, 5)
    rng = np.random.default_rng(1)
    perm = rng.permutation(len(y))
    tr = perm[:8]; test = perm[300:]; pool = perm[8:300]
    # make sure the initial set holds all three classes
    for c in range(3):
        if c not in y[tr]:
            j = [i for i in pool if y[i] == c][0]
            tr = np.append(tr, j); pool = pool[pool != j]
    Xt, yt = X[test], y[test]
    m0 = fit_lr(X[tr], y[tr])
    acc0 = m0.score(Xt, yt)
    rnd = rng.choice(pool, 11, replace=False)
    m1 = fit_lr(X[np.r_[tr, rnd]], y[np.r_[tr, rnd]])
    acc1 = m1.score(Xt, yt)
    cur = list(tr); remaining = list(pool); queried = []
    for _ in range(11):
        mm = fit_lr(X[cur], y[cur])
        pr = mm.predict_proba(X[remaining])
        j = remaining[int(np.argmax(margin_score(pr)))]
        queried.append(j); cur.append(j); remaining.remove(j)
    m2 = fit_lr(X[cur], y[cur])
    acc2 = m2.score(Xt, yt)
    xx, yy = np.meshgrid(np.linspace(X[:, 0].min() - .5, X[:, 0].max() + .5, 250), np.linspace(X[:, 1].min() - .5, X[:, 1].max() + .5, 250))
    fig, axes = plt.subplots(1, 3, figsize=(10.0, 3.1), sharex=True, sharey=True)
    cols = np.array([RED, BLUE, GREEN])
    for ax, mod, qs, acc, title in [(axes[0], m0, [], acc0, "(a) initial training set"), (axes[1], m1, rnd, acc1, "(b) + 11 random points"),
                                    (axes[2], m2, queried, acc2, "(c) + 11 margin-sampled points")]:
        Z = mod.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
        ax.contourf(xx, yy, Z, levels=[-.5, .5, 1.5, 2.5], colors=["#f6c9c9", "#c9d8f2", "#cdeccd"], alpha=0.8)
        ax.scatter(X[pool, 0], X[pool, 1], s=6, color="#888888", alpha=0.6, label="pool")
        used = np.r_[tr] if len(qs) == 0 else tr
        ax.scatter(X[tr, 0], X[tr, 1], s=26, c=cols[y[tr]], edgecolor="black", label="initial")
        if len(qs):
            ax.scatter(X[qs, 0], X[qs, 1], s=40, c=cols[y[qs]], edgecolor="black", marker="s", label="queried")
        ax.set_title("%s\ntest accuracy %.3f" % (title, acc), fontsize=9)
    axes[0].legend(fontsize=7, loc="lower left"); axes[2].legend(fontsize=7, loc="lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig34-15", out)
    return dict(acc0=acc0, acc_random=acc1, acc_margin=acc2)


def gp_posterior(X, y, Xs, ell=0.15, sf=1.0, sn=0.05):
    k = lambda a, b: sf ** 2 * np.exp(-0.5 * (a[:, None] - b[None, :]) ** 2 / ell ** 2)
    K = k(X, X) + sn ** 2 * np.eye(len(X))
    L = np.linalg.cholesky(K)
    Ks = k(X, Xs)
    a = np.linalg.solve(L.T, np.linalg.solve(L, y))
    mu = Ks.T @ a
    V = np.linalg.solve(L, Ks)
    var = sf ** 2 - (V ** 2).sum(0)
    return mu, np.maximum(var, 1e-12)


def fig_34_16(out=None):
    """Figure 34.16: active learning (query where the predictive variance is largest) versus Bayesian optimisation (probability of improvement)."""
    f = lambda x: np.sin(3 * np.pi * x) * np.exp(-1.2 * x) + 0.3 * x
    xs = np.linspace(0, 1, 400)
    rng = np.random.default_rng(3)
    X0 = np.array([0.1, 0.5, 0.9]); y0 = f(X0)
    Xa, ya = X0.copy(), y0.copy(); Xb, yb = X0.copy(), y0.copy()
    nq = 7
    qa, qb = [], []
    for _ in range(nq):
        mu, var = gp_posterior(Xa, ya, xs)
        j = int(np.argmax(var)); Xa = np.append(Xa, xs[j]); ya = np.append(ya, f(xs[j])); qa.append(xs[j])
        mu, var = gp_posterior(Xb, yb, xs)
        pi = stats.norm.cdf((mu - yb.max()) / np.sqrt(var))
        j = int(np.argmax(pi)); Xb = np.append(Xb, xs[j]); yb = np.append(yb, f(xs[j])); qb.append(xs[j])
    fig, axes = plt.subplots(2, 2, figsize=(8.6, 4.8), sharex=True)
    for col, (X, y, qs, nm) in enumerate([(Xa, ya, qa, "(a) active learning"), (Xb, yb, qb, "(b) Bayesian optimisation")]):
        mu, var = gp_posterior(X, y, xs)
        ax = axes[0, col]
        ax.plot(xs, f(xs), color="black", lw=1, label="true function")
        ax.plot(xs, mu, color=BLUE, label="predictive mean")
        ax.fill_between(xs, mu - 1.96 * np.sqrt(var), mu + 1.96 * np.sqrt(var), color=BLUE, alpha=0.2, label="95% band")
        ax.scatter(X[:3], y[:3], color="black", zorder=3, s=22, label="initial")
        ax.scatter(X[3:], y[3:], color=RED, zorder=3, s=22, label="queried")
        ax.set_title(nm, fontsize=9.5)
        ax = axes[1, col]
        Xp, yp = X[:-1], y[:-1]
        mu_p, var_p = gp_posterior(Xp, yp, xs)
        if col == 0:
            ax.plot(xs, var_p, color=GREEN); ax.set_ylabel("predictive variance")
        else:
            ax.plot(xs, stats.norm.cdf((mu_p - yp.max()) / np.sqrt(var_p)), color=GREEN); ax.set_ylabel("prob. of improvement")
        ax.axvline(X[-1], color=RED, ls=":")
        ax.set_xlabel("$x$")
    axes[0, 0].legend(fontsize=7)
    fig.tight_layout()
    savefig(fig, CH, "fig34-16", out)
    return dict(qa=qa, qb=qb)


def _digits_split(seed=0, n_test=600):
    from sklearn.datasets import load_digits
    d = load_digits()
    X = d.data / 16.0; y = d.target
    rng = np.random.default_rng(seed)
    perm = rng.permutation(len(y))
    return X, y, perm[:n_test], perm[n_test:]


def fig_34_17(out=None):
    """Figure 34.17: least-confidence, entropy and margin scores disagree about which candidate to query (digits)."""
    X, y, test, rest = _digits_split(0)
    rng = np.random.default_rng(2)
    tr = rest[:80]
    pool = rest[80:600]
    m = fit_lr(X[tr], y[tr])
    P = m.predict_proba(X[pool])
    # find a triple of pool points such that least-confidence, entropy and margin each prefer a different one
    lc, en, mg = least_conf(P), entropy(P), margin_score(P)
    best = None
    top = np.argsort(-(lc + en))[:40]
    for i in top:
        for j in top:
            for k in top:
                if len({i, j, k}) < 3:
                    continue
                if lc[i] > max(lc[j], lc[k]) and en[j] > max(en[i], en[k]) and mg[k] > max(mg[i], mg[j]):
                    gap = min(lc[i] - max(lc[j], lc[k]), en[j] - max(en[i], en[k]), mg[k] - max(mg[i], mg[j]))
                    if best is None or gap > best[0]:
                        best = (gap, i, j, k)
    if best is None:
        best = (0, int(np.argmax(lc)), int(np.argmax(en)), int(np.argmax(mg)))
    idx = best[1:]
    fig, axes = plt.subplots(2, 3, figsize=(9.6, 4.6), gridspec_kw=dict(height_ratios=[1.35, 1]))
    for c, i in enumerate(idx):
        ax = axes[0, c]
        p = P[i]; order = np.argsort(-p)
        colors = ["#bbbbbb"] * 10
        colors[order[0]] = "#444444"; colors[order[1]] = "#999999"
        ax.bar(np.arange(10), p, color=colors)
        ax.set_xticks(np.arange(10)); ax.set_ylim(0, 0.8)
        ax.set_title("candidate %d (true digit %d)" % (c + 1, y[pool[i]]), fontsize=9)
        if c == 0:
            ax.set_ylabel("predicted probability")
        ax2 = axes[1, c]
        vals = [en[i], mg[i], lc[i]]
        ax2.barh(["entropy", "margin $p_2-p_1$", "least confident"], vals, color=[BLUE, ORANGE, GREEN])
        for k, v in enumerate(vals):
            ax2.text(v + 0.02 if v >= 0 else 0.02, k, "%.3f" % v, va="center", fontsize=8)
        ax2.set_xlim(min(-0.9, min(vals) - 0.05), 2.4)
        ax2.axvline(0, color="black", lw=0.6)
    fig.tight_layout()
    savefig(fig, CH, "fig34-17", out)
    return dict(idx=[int(i) for i in idx], lc=[float(lc[i]) for i in idx], en=[float(en[i]) for i in idx], mg=[float(mg[i]) for i in idx])


def al_curve_toy(strategy, seed, n_init=6, n_q=40, model="rf"):
    """Accuracy against the number of queries on the simulated 3-class problem (random forest or committee)."""
    from sklearn.ensemble import RandomForestClassifier
    from sklearn.linear_model import LogisticRegression
    X, y = make_toy3(600, 11)
    rng = np.random.default_rng(seed)
    perm = rng.permutation(len(y))
    test = perm[:300]; rest = perm[300:]
    tr = []
    for c in range(3):                                          # two labelled points per class to start
        tr += [i for i in rest if y[i] == c][:2]
    tr += [i for i in rest if i not in tr][:n_init - len(tr)]
    pool = [i for i in rest if i not in tr]
    accs = []
    for q in range(n_q + 1):
        rf = RandomForestClassifier(n_estimators=40, random_state=seed + q).fit(X[tr], y[tr])
        accs.append(rf.score(X[test], y[test]))
        if q == n_q:
            break
        if strategy == "random":
            j = pool[int(rng.integers(len(pool)))]
        elif strategy == "margin":
            P = np.zeros((len(pool), 3)); P[:, rf.classes_] = rf.predict_proba(X[pool])
            j = pool[int(np.argmax(margin_score(P)))]
        elif strategy == "qbc":
            lr = LogisticRegression(max_iter=1000).fit(X[tr], y[tr])
            votes = np.zeros((len(pool), 3))
            for mod in (rf, lr):
                pr = mod.predict(X[pool])
                votes[np.arange(len(pool)), pr] += 1
            Q = votes / 2.0                                     # divide by the number of members K = 2
            # break ties with the committee's average probability margin
            Pavg = np.zeros((len(pool), 3)); Pavg[:, rf.classes_] = rf.predict_proba(X[pool])
            Pavg[:, lr.classes_] += lr.predict_proba(X[pool])
            score = entropy(Q) + 1e-3 * (-margin_score(Pavg / 2))
            j = pool[int(np.argmax(score))]
        tr.append(j); pool.remove(j)
    return np.array(accs)


def fig_34_18(out=None):
    """Figure 34.18: a random forest on a simulated three-class problem; accuracy against the number of queries."""
    from sklearn.ensemble import RandomForestClassifier
    X, y = make_toy3(600, 11)
    rng = np.random.default_rng(0)
    perm = rng.permutation(len(y))
    fig, axes = plt.subplots(1, 2, figsize=(9.2, 3.3), gridspec_kw=dict(width_ratios=[1, 1.35]))
    ax = axes[0]
    tr = perm[300:306]; pool = perm[306:]
    rf = RandomForestClassifier(n_estimators=40, random_state=0).fit(X[tr], y[tr]) if len(set(y[tr])) > 1 else None
    xx, yy = np.meshgrid(np.linspace(X[:, 0].min() - .5, X[:, 0].max() + .5, 200), np.linspace(X[:, 1].min() - .5, X[:, 1].max() + .5, 200))
    if rf is not None:
        Z = rf.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
        ax.contourf(xx, yy, Z, levels=[-.5, .5, 1.5, 2.5], colors=["#f6c9c9", "#c9d8f2", "#cdeccd"], alpha=0.8)
    ax.scatter(X[pool, 0], X[pool, 1], s=6, color="#888888", alpha=0.6, label="pool")
    ax.scatter(X[tr, 0], X[tr, 1], s=30, c=np.array([RED, BLUE, GREEN])[y[tr]], edgecolor="black", label="train")
    ax.set_xlabel("$x_0$"); ax.set_ylabel("$x_1$"); ax.set_title("(a) random forest, 6 labelled points", fontsize=9.5); ax.legend(fontsize=7.5)
    ax = axes[1]
    nseed = 5
    curves = {s: np.array([al_curve_toy(s, seed) for seed in range(nseed)]) for s in ["margin", "qbc", "random"]}
    q = np.arange(curves["margin"].shape[1])
    ax.plot(q, curves["margin"].mean(0), color=BLUE, label="margin sampling (random forest)")
    ax.plot(q, curves["qbc"].mean(0), color=RED, label="query by committee (forest + logistic)")
    for r in curves["random"]:
        ax.plot(q, r, color="#bbbbbb", lw=0.7)
    ax.plot(q, curves["random"].mean(0), color="black", ls="--", label="random (mean of 5 runs)")
    ax.set_xlabel("number of points queried"); ax.set_ylabel("test accuracy"); ax.set_title("(b) mean over 5 repetitions", fontsize=9.5); ax.legend(fontsize=7.5, loc="lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig34-18", out)
    return {k: v.mean(0)[[0, 10, 20, 40]].tolist() for k, v in curves.items()}


# BALD and BatchBALD with a small dropout network (Figure 34.20)
def bald_scores(P):
    """P[s, n, c]: S posterior samples of the class probabilities of n pool points. BALD = H(mean p) - mean H(p)."""
    return entropy(P.mean(0)) - entropy(P).mean(0)


def batchbald_greedy(P, B, pool_chunk=40):
    """Greedy BatchBALD (34.104-34.108) with exact enumeration of the joint labels of the batch.

    P[s, n, c]. Returns the list of chosen indices. The joint predictive of the chosen set is kept as an array
    J[s, K^k] and extended by each candidate; the score is H(y_1:B) - sum_i E_w H(y_i | w)."""
    S, N, C = P.shape
    Hc = entropy(P).mean(0)                                    # E_w H(y_i | w)
    chosen = []
    J = np.ones((S, 1))
    for k in range(B):
        scores = np.full(N, -np.inf)
        for st in range(0, N, pool_chunk):
            ids = np.arange(st, min(N, st + pool_chunk))
            new = J[:, None, :, None] * P[:, ids, None, :]          # [S, chunk, K^k, C]
            marg = new.mean(0).reshape(len(ids), -1)                # joint predictive of the extended set
            Hj = entropy(marg, axis=1)
            scores[ids] = Hj - (Hc[chosen].sum() + Hc[ids])
        for j in chosen:
            scores[j] = -np.inf
        j = int(np.argmax(scores))
        chosen.append(j)
        J = (J[:, :, None] * P[:, j, None, :]).reshape(S, -1)
    return chosen


def _train_dropout_net(Xtr, ytr, seed, epochs=200, p=0.25):
    import torch
    torch.manual_seed(seed)
    net = torch.nn.Sequential(torch.nn.Linear(64, 64), torch.nn.ReLU(), torch.nn.Dropout(p), torch.nn.Linear(64, 10))
    opt = torch.optim.Adam(net.parameters(), lr=0.01, weight_decay=1e-3)
    Xt = torch.tensor(Xtr, dtype=torch.float32); yt = torch.tensor(ytr)
    net.train()
    for _ in range(epochs):
        opt.zero_grad()
        loss = torch.nn.functional.cross_entropy(net(Xt), yt)
        loss.backward(); opt.step()
    return net


def _mc_probs(net, X, S, seed):
    import torch
    torch.manual_seed(seed)
    net.train()                                                  # keep dropout on
    Xt = torch.tensor(X, dtype=torch.float32)
    with torch.no_grad():
        return np.stack([torch.softmax(net(Xt), -1).numpy() for _ in range(S)])


def al_digits_run(method, seed, rounds=20, B=4, n_pool=500, S=24, init_per_class=2):
    from sklearn.datasets import load_digits
    torch_seed = 100 + seed
    d = load_digits(); X = d.data / 16.0; y = d.target
    rng = np.random.default_rng(seed)
    perm = rng.permutation(len(y))
    test = perm[:500]; rest = perm[500:]
    tr = []
    for c in range(10):
        tr += [i for i in rest if y[i] == c][:init_per_class]
    pool = [i for i in rest if i not in tr][:n_pool]
    accs, picks = [], []
    import torch
    torch.set_num_threads(1)
    for r in range(rounds + 1):
        net = _train_dropout_net(X[tr], y[tr], torch_seed + r)
        net.eval()
        with torch.no_grad():
            accs.append(float((net(torch.tensor(X[test], dtype=torch.float32)).argmax(1).numpy() == y[test]).mean()))
        if r == rounds:
            break
        if method == "random":
            sel = list(rng.choice(len(pool), B, replace=False))
        else:
            P = _mc_probs(net, X[pool], S, torch_seed + 7 * r)
            if method == "bald":
                sel = list(np.argsort(-bald_scores(P))[:B])
            else:
                top = np.argsort(-bald_scores(P))[:150]          # pre-filter by BALD to keep the enumeration cheap
                sub = batchbald_greedy(P[:, top, :], B)
                sel = [int(top[j]) for j in sub]
        batch = [pool[j] for j in sel]
        if r < 3:
            picks.append(batch)
        tr += batch
        pool = [i for i in pool if i not in batch]
    return np.array(accs), picks


def fig_34_20(out=None):
    """Figure 34.20: BALD versus BatchBALD versus random on the digits data with a dropout network (scaled down)."""
    os.makedirs(CACHE_DIR, exist_ok=True)
    path = os.path.join(CACHE_DIR, "ch34_fig20.npz")
    seeds = [0, 1, 2]
    methods = ["random", "bald", "batchbald"]
    if os.path.exists(path):
        z = np.load(path, allow_pickle=True)
        accs = z["accs"].item(); picks = z["picks"].item()
    else:
        accs = {m: [] for m in methods}; picks = {}
        for m in methods:
            for s in seeds:
                a, pk = al_digits_run(m, s)
                accs[m].append(a)
                if s == 0:
                    picks[m] = pk
        np.savez(path, accs=accs, picks=picks)
    from sklearn.datasets import load_digits
    D = load_digits().images
    fig = plt.figure(figsize=(9.6, 5.4))
    gs = fig.add_gridspec(2, 3, height_ratios=[1, 1.1])
    for col, m in enumerate(["bald", "batchbald"]):
        sub = gs[0, col].subgridspec(3, 4, wspace=0.05, hspace=0.08)
        for r in range(3):
            for c in range(4):
                ax = fig.add_subplot(sub[r, c])
                ax.imshow(D[picks[m][r][c]], cmap="gray_r"); ax.set_xticks([]); ax.set_yticks([])
                if r == 0 and c == 0:
                    ax.set_title("(%s) %s: batches 1 to 3" % ("ab"[col], "BALD" if m == "bald" else "BatchBALD"), fontsize=9, loc="left")
    ax = fig.add_subplot(gs[0, 2]); ax.axis("off")
    ax.text(0.0, 0.5, "Each row is one batch of 4 queried\ndigits (first run of the three).\nPanel (c) averages all three runs.", fontsize=8.5, va="center")
    ax = fig.add_subplot(gs[1, :])
    q = 20 + 4 * np.arange(len(accs["random"][0]))
    for m, col, lab in [("random", GREY, "random"), ("bald", ORANGE, "BALD"), ("batchbald", RED, "BatchBALD")]:
        A = np.array(accs[m])
        ax.plot(q, 100 * A.mean(0), color=col, label=lab)
        ax.fill_between(q, 100 * (A.mean(0) - A.std(0)), 100 * (A.mean(0) + A.std(0)), color=col, alpha=0.15)
    ax.set_xlabel("number of labelled points"); ax.set_ylabel("test accuracy (%)"); ax.set_title("(c) accuracy against labels used (mean and sd over 3 seeds)", fontsize=9.5); ax.legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig34-20", out)
    return {m: np.array(accs[m]).mean(0)[[0, 5, 10, 20]].tolist() for m in methods}


# ====================================================================== data export for the demos
def export_data(out=None):
    """Reference numbers the demos reproduce (written to ../data/ch34-*.json)."""
    os.makedirs(DATA_OUT, exist_ok=True)
    ex = ab_book_example()
    presets = []
    for N, m, tau, sigma in [(100000, 0.68, 0.03, np.sqrt(0.68 * 0.32)), (100000, 0.68, 0.03, 1.0), (100000, 0.68, 0.10, np.sqrt(0.68 * 0.32)),
                             (5000, 0.68, 0.03, np.sqrt(0.68 * 0.32)), (1000000, 0.68, 0.03, np.sqrt(0.68 * 0.32))]:
        ns = ab_nstar(N, tau, sigma)
        presets.append(dict(N=N, m=m, tau=tau, sigma=float(sigma), nstar=ns, total=float(ab_expected_reward(round(ns), N, m, tau, sigma)),
                            err=float(ab_error_rate(round(ns), tau, sigma)), regret=float(ab_regret(ns, N, tau, sigma))))
    sim = simulate_ab(2284, 100000, 0.68, 0.03, np.sqrt(0.68 * 0.32), reps=400_000, seed=1)
    with open(os.path.join(DATA_OUT, "ch34-ab.json"), "w") as f:
        json.dump(dict(book=ex, presets=presets, sim=dict(mean=float(sim[0]), se=float(sim[1]), err=float(sim[2]))), f, indent=1)
    # bandits: reference mean regret at T from the Python simulation, for the demo presets
    bp = []
    for name, mu, T in [("easy", [0.7, 0.4, 0.3], 1000), ("close", [0.5, 0.45, 0.4, 0.3], 2000), ("many", [0.6, 0.5, 0.5, 0.4, 0.4, 0.3, 0.3, 0.2], 2000)]:
        d = dict(name=name, mu=mu, T=T, lr=lai_robbins_const(mu), regret={})
        for key in ["greedy", "eps", "ucb1", "bayesucb", "ts"]:
            m_, se = simulate_bandit(key, mu, T, 400, seed=5)
            d["regret"][key] = dict(mean=float(m_[-1]), se=float(se[-1]))
        bp.append(d)
    with open(os.path.join(DATA_OUT, "ch34-bandit.json"), "w") as f:
        json.dump(dict(presets=bp), f, indent=1)
    # MDP references
    P, R = chain_mdp(3)
    chain = {}
    for g in [0.0, 0.5, 0.9, 1.0]:
        v, pol, it, _ = value_iteration(P, R, g, tol=1e-12, max_iter=500)
        chain[str(g)] = dict(Q=q_from_v(P, R, g, v)[1:4].tolist(), V=v.tolist(), iters=it)
    Pg, Rg, cells, idx = grid_mdp()
    gg = {}
    for g in [0.5, 0.9, 0.99]:
        v, pol, it, _ = value_iteration(Pg, Rg, g, tol=1e-10)
        vp, pip, itp, _ = policy_iteration(Pg, Rg, g)
        gg[str(g)] = dict(V=v.tolist(), policy=pol.tolist(), vi_iters=it, pi_iters=itp)
    with open(os.path.join(DATA_OUT, "ch34-mdp.json"), "w") as f:
        json.dump(dict(chain=chain, grid=dict(layout=GRID_LAYOUT, slip=0.2, step=-0.04, cells=[list(c) for c in cells], results=gg)), f, indent=1)
    print("wrote data/ch34-ab.json, ch34-bandit.json, ch34-mdp.json")


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


FIGURES = {"34.2": fig_34_2, "34.5": fig_34_5, "34.6": fig_34_6, "34.8": fig_34_8, "34.9": fig_34_9, "34.10": fig_34_10,
           "34.13": fig_34_13, "34.15": fig_34_15, "34.16": fig_34_16, "34.17": fig_34_17, "34.18": fig_34_18, "34.20": fig_34_20,
           "34.21": fig_34_21, "34.22": fig_34_22, "34.23": fig_34_23, "data": fig_export}

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