"""Murphy (2022), Chapter 22: Recommender Systems.

Companion code for Chapter 22 of K. P. Murphy, Probabilistic Machine Learning: An Introduction
(MIT Press, 2022; April 2025 draft), pp. 741-751, written from scratch with numpy, scipy and
matplotlib, to be read next to the lecture notes (../ch22-recommender-systems.html).

Methods
* Section 22.1.2, collaborative filtering: user-based neighbourhood prediction (22.1), with the
  normalisation the book leaves out (knn_predict).
* Section 22.1.3, matrix factorisation: the biased factorisation model (22.4), regularised least
  squares (22.5), alternating least squares (als), stochastic gradient descent with the updates
  (22.6)-(22.9) (sgd_mf), the SVD of the zero-filled matrix used for MovieLens (svd_zero_fill, with
  the 1/p rescaling that undoes the shrinkage), probabilistic matrix factorisation (22.10) as the MAP
  estimate of the same model.
* Section 22.1.4, autoencoders: parameter counts of the item-based and user-based AutoRec models.
* Section 22.2, implicit feedback: Bayesian personalised ranking (22.13)-(22.14) trained by SGD
  on sampled triples (bpr_train), with the hinge variant (22.16); the factorisation machine (22.17)
  with the O(KD) evaluation (22.18)-(22.20) (fm_predict, fm_sgd); the generalised matrix
  factorisation pathway of neural matrix factorisation (22.22)-(22.24).
* Section 22.3, side information: cold start with an FM that sees the item genre (fm_cold_start).
* Section 22.4, exploration and exploitation: a click bandit with greedy, epsilon-greedy, UCB1 and
  Thompson sampling (bandit_run), and inverse propensity scoring of logged data (ips_experiment).

Data. The book uses the Netflix data (no longer available) and MovieLens-1M (not available offline),
so every ratings matrix here is simulated by simulate_ratings: 300 users, 200 items in six genres,
true latent dimension 3, user and item baselines, 12 percent of entries observed with a
popularity-skewed pattern, ratings rounded to {1,...,5}. The implicit-feedback data of bpr_data are
simulated as well. Seeds are fixed, so every number is reproducible. Figures that show items
therefore show simulated items (labelled by genre), not movie titles.

Figures. Reproduced here: 22.1 (a small ratings matrix and its bipartite graph, with the user
similarities computed), 22.2 (item embeddings of a K = 2 factorisation, one colour per genre; the
book's Figure 22.2 is taken from Koren et al. and the stand-in uses simulated items), 22.3 (a
fragment of the observed matrix and the zero-filled SVD predictions), 22.4 (top rated items of one
user and the top predictions), 22.6 (a computed design matrix with side information). Skipped, with the reason:
  22.5   the neural matrix factorisation diagram (a hand-drawn network schematic).
Supplementary figures for the gaps filled in the notes:
  22.S1  test RMSE of five predictors, and the (K, lambda) map of ALS;
  22.S2  ALS against SGD, epoch by epoch;
  22.S3  the zero-filled SVD with and without the 1/p rescaling, against K;
  22.S4  informative missingness: bias of the naive mean, of ALS, and the inverse-propensity fix;
  22.S5  Bayesian personalised ranking against the popularity ranking (AUC and hit rate);
  22.S6  cold start: an FM with item genre against an id-only model;
  22.S7  regret of four exploration policies in a click bandit;
  22.S8  the sampling distribution of the naive and the inverse-propensity estimates of a new policy.
Run `python3 ch22_recommender_systems.py --list`, `python3 ch22_recommender_systems.py` (all figures,
about three minutes) or `python3 ch22_recommender_systems.py --fig 22.3`. Files go to ../img/ch22/;
the data used by the browser demonstrations go to ../data/ch22-*.json.
"""
import json
import math
import os
import sys

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")

import numpy as np

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

CH = 22
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
GENRES = ["Comedy", "Horror", "Costume drama", "Arthouse", "Action", "Film noir"]
GCOL = [ORANGE, RED, PURPLE, BLUE, GREEN, GREY]


# =========================================================================== shared random numbers
class Mulberry:
    """The mulberry32 generator with Box-Muller normals used by the browser demonstrations
    (demo-kit.js), so that a demonstration and this code can run on the same random stream."""

    M32 = 0xFFFFFFFF

    def __init__(self, seed):
        self.a = seed & self.M32
        self.spare = None

    @staticmethod
    def _imul(x, y):
        return (x * y) & 0xFFFFFFFF

    def u(self):
        self.a = (self.a + 0x6D2B79F5) & self.M32
        a = self.a
        t = self._imul(a ^ (a >> 15), 1 | a)
        t = ((t + self._imul(t ^ (t >> 7), 61 | t)) & self.M32) ^ t
        return ((t ^ (t >> 14)) & self.M32) / 4294967296.0

    def pos(self):
        x = 0.0
        while x == 0.0:
            x = self.u()
        return x

    def norm(self):
        if self.spare is not None:
            s, self.spare = self.spare, None
            return s
        r = math.sqrt(-2.0 * math.log(self.pos()))
        th = 2.0 * math.pi * self.u()
        self.spare = r * math.sin(th)
        return r * math.cos(th)

    def randint(self, n):
        return int(math.floor(self.u() * n))


# =========================================================================== data
def simulate_ratings(seed=22, M=300, N=200, density=0.12, noise=0.5):
    """A simulated ratings matrix with the structure of Section 22.1.

    Returns a dict with the full noisy rating matrix R (M x N, values in 1..5), the mask Obs of the
    observed entries, the true factors, the baselines and the genre of every item."""
    rng = np.random.default_rng(seed)
    G = len(GENRES)
    ang = 2 * np.pi * np.arange(G) / G + 0.3
    centers = np.stack([np.cos(ang), np.sin(ang), np.zeros(G)], 1)
    genre = rng.integers(0, G, N)
    V = centers[genre] + rng.normal(0, 0.22, (N, 3)) * np.array([1, 1, 0]) + np.array([0, 0, 1]) * rng.normal(0, 0.3, (N, 1))
    U = rng.normal(0, 0.8, (M, 3))
    b = rng.normal(0, 0.35, M)
    c = rng.normal(0, 0.4, N)
    mu = 3.4
    mean = mu + b[:, None] + c[None, :] + U @ V.T
    R = np.clip(np.round(mean + rng.normal(0, noise, (M, N))), 1, 5)
    act = np.exp(rng.normal(0, 0.5, M))
    pop = (np.argsort(rng.permutation(N)) + 1.0) ** -0.5
    P0 = np.outer(act, pop)
    lo, hi = 0.0, 100.0
    for _ in range(60):
        s = 0.5 * (lo + hi)
        if np.minimum(1, s * P0).mean() > density:
            hi = s
        else:
            lo = s
    P = np.minimum(1, lo * P0)
    Obs = rng.random((M, N)) < P
    for u in range(M):
        while Obs[u].sum() < 6:
            Obs[u, rng.integers(0, N)] = True
    return dict(R=R, Obs=Obs, U=U, V=V, b=b, c=c, mu=mu, mean=mean, genre=genre, P=P, noise=noise)


def split_observed(D, test_frac=0.2, seed=1):
    """Random split of the observed entries into training and test triples (u, i, r)."""
    rng = np.random.default_rng(seed)
    uu, ii = np.nonzero(D["Obs"])
    r = D["R"][uu, ii]
    perm = rng.permutation(len(uu))
    nte = int(round(test_frac * len(uu)))
    te, tr = perm[:nte], perm[nte:]
    return (uu[tr], ii[tr], r[tr]), (uu[te], ii[te], r[te])


def rmse(pred, y):
    return float(np.sqrt(np.mean((np.asarray(pred) - np.asarray(y)) ** 2)))


# =========================================================================== Section 22.1.2
def knn_predict(train, M, N, test_pairs, k=20, shrink=5.0):
    """User-based collaborative filtering, (22.1) with the normalisation: for a pair (u, i)
        yhat = mean_u + sum_{u'} sim(u,u') (Y_{u'i} - mean_{u'}) / sum_{u'} |sim(u,u')|,
    over the k most similar users who rated i. sim is the cosine similarity of the mean-centred
    rating vectors on the co-rated items, shrunk by n/(n+shrink) when few items are shared."""
    u, i, r = train
    Y = np.zeros((M, N))
    O = np.zeros((M, N), bool)
    Y[u, i] = r
    O[u, i] = True
    cnt = O.sum(1)
    mean_u = np.where(cnt > 0, Y.sum(1) / np.maximum(cnt, 1), r.mean())
    Yc = np.where(O, Y - mean_u[:, None], 0.0)
    num = Yc @ Yc.T
    nrm = np.sqrt((Yc ** 2) @ O.T.astype(float))     # norm of u's centred ratings on items rated by u'
    sim = num / np.maximum(nrm * nrm.T, 1e-12)
    co = O.astype(float) @ O.T.astype(float)
    sim = sim * co / (co + shrink)
    np.fill_diagonal(sim, 0.0)
    out = []
    for uu, ii in test_pairs:
        cand = np.nonzero(O[:, ii])[0]
        if len(cand) == 0:
            out.append(mean_u[uu])
            continue
        s = sim[uu, cand]
        top = np.argsort(-np.abs(s))[:k]
        s, cand = s[top], cand[top]
        den = np.abs(s).sum()
        out.append(mean_u[uu] + (s @ Yc[cand, ii]) / den if den > 1e-12 else mean_u[uu])
    return np.array(out)


# =========================================================================== Section 22.1.3
def make_init(N, Kmax=8, seed=5):
    """The fixed random initial item factors of the demonstration, rounded to 6 decimals."""
    return np.round(np.random.default_rng(seed).normal(0, 0.1, (N, Kmax)), 6)


def als(train, M, N, K, lam, iters, V0, biases=True, test=None):
    """Alternating least squares for  sum (y - mu - b_u - c_i - u'v)^2 + lam (sum b^2 + c^2 + |u|^2 + |v|^2).

    Each half-step is a ridge regression for every user (or item) on the factors of the other side
    (gap 22.2). Initial V = V0[:, :K], U = b = c = 0. Returns the parameters and the history of
    (train RMSE, test RMSE) after every full iteration (iteration 0 is the baseline mu)."""
    u, i, r = train
    mu = float(r.mean())
    V = V0[:, :K].copy() if K > 0 else np.zeros((N, 0))
    U = np.zeros((M, K))
    b = np.zeros(M)
    c = np.zeros(N)
    by_u = [np.nonzero(u == m)[0] for m in range(M)]
    by_i = [np.nonzero(i == n)[0] for n in range(N)]
    hist = []

    def pred(uu, ii):
        p = mu + (U[uu] * V[ii]).sum(1)
        return p + (b[uu] + c[ii] if biases else 0.0)

    def record():
        h = [rmse(pred(u, i), r)]
        if test is not None:
            h.append(rmse(pred(test[0], test[1]), test[2]))
        hist.append(h)

    record()
    for _ in range(iters):
        for m in range(M):                            # user step
            idx = by_u[m]
            if len(idx) == 0:
                continue
            F = V[i[idx]]
            t = r[idx] - mu - (c[i[idx]] if biases else 0.0)
            if biases:
                F = np.hstack([np.ones((len(idx), 1)), F])
            th = np.linalg.solve(F.T @ F + lam * np.eye(F.shape[1]), F.T @ t)
            if biases:
                b[m], U[m] = th[0], th[1:]
            else:
                U[m] = th
        for n in range(N):                            # item step
            idx = by_i[n]
            if len(idx) == 0:
                continue
            F = U[u[idx]]
            t = r[idx] - mu - (b[u[idx]] if biases else 0.0)
            if biases:
                F = np.hstack([np.ones((len(idx), 1)), F])
            th = np.linalg.solve(F.T @ F + lam * np.eye(F.shape[1]), F.T @ t)
            if biases:
                c[n], V[n] = th[0], th[1:]
            else:
                V[n] = th
        record()
    return dict(mu=mu, b=b, c=c, U=U, V=V, hist=np.array(hist), biases=biases)


def mf_predict(P, uu, ii):
    return P["mu"] + (P["U"][uu] * P["V"][ii]).sum(1) + (P["b"][uu] + P["c"][ii] if P["biases"] else 0.0)


def objective_522(P, train, lam):
    """The regularised objective (22.5) with the penalty applied once per parameter."""
    u, i, r = train
    e = r - mf_predict(P, u, i)
    return float(e @ e + lam * (np.sum(P["b"] ** 2) + np.sum(P["c"] ** 2) + np.sum(P["U"] ** 2) + np.sum(P["V"] ** 2)))


def sgd_mf(train, M, N, K, lam, eta, epochs, seed=0, test=None):
    """Stochastic gradient descent with the updates (22.6)-(22.9). Each step samples one observed
    entry (u, i), forms e = y - yhat and moves b_u, c_i, u_u, v_i; the penalty acts on the
    parameters touched by that entry (the per-observation reading of (22.5))."""
    u, i, r = train
    rng = np.random.default_rng(seed)
    mu = float(r.mean())
    U = rng.normal(0, 0.1, (M, K))
    V = rng.normal(0, 0.1, (N, K))
    b = np.zeros(M)
    c = np.zeros(N)
    hist = []
    for ep in range(epochs + 1):
        if ep > 0:
            for n in rng.permutation(len(u)):
                a, j = u[n], i[n]
                e = r[n] - (mu + b[a] + c[j] + U[a] @ V[j])
                b[a] += eta * (e - lam * b[a])
                c[j] += eta * (e - lam * c[j])
                ua = U[a].copy()
                U[a] += eta * (e * V[j] - lam * U[a])
                V[j] += eta * (e * ua - lam * V[j])
        h = [rmse(mu + b[u] + c[i] + (U[u] * V[i]).sum(1), r)]
        if test is not None:
            h.append(rmse(mu + b[test[0]] + c[test[1]] + (U[test[0]] * V[test[1]]).sum(1), test[2]))
        hist.append(h)
    return dict(mu=mu, b=b, c=c, U=U, V=V, hist=np.array(hist), biases=True)


def svd_zero_fill(train, M, N, K, rescale=False, p=None):
    """Zero-filled SVD (the MovieLens recipe of Section 22.1.3.3): missing entries are set to 0 and
    the best rank-K approximation (Eckart-Young) is the prediction. With rescale=True the result is
    divided by the observed fraction p (gap 22.6), which undoes the shrinkage towards 0."""
    u, i, r = train
    Y = np.zeros((M, N))
    Y[u, i] = r
    U, s, Vt = np.linalg.svd(Y, full_matrices=False)
    Z = (U[:, :K] * s[:K]) @ Vt[:K]
    if rescale:
        p = len(r) / (M * N) if p is None else p
        Z = Z / p
    return Z


def procrustes(A, B):
    """Orthogonal matrix Q minimising |A Q - B|_F (A, B: n x k)."""
    U, _, Vt = np.linalg.svd(A.T @ B)
    return U @ Vt


# =========================================================================== Section 22.2
def bpr_data(seed=7, M=150, N=100, K=3, tau=0.7):
    """Simulated implicit feedback: each user selects 10 to 25 items, sampled without replacement
    (Gumbel top-k) with probability governed by an affinity u'v + popularity. One positive per user
    is held out for testing. Returns dict(train=[(u,i)], test=[(u,i)], pos=list of train item sets)."""
    rng = np.random.default_rng(seed)
    Ut = rng.normal(0, 1.0, (M, K))
    Vt = rng.normal(0, 1.0, (N, K))
    pop = rng.normal(0, 1.0, N)
    S = Ut @ Vt.T + 0.8 * pop[None, :]
    train, test, pos = [], [], []
    for m in range(M):
        n_m = int(rng.integers(10, 26))
        g = S[m] / tau + rng.gumbel(size=N)
        sel = list(np.argsort(-g)[:n_m])
        rng.shuffle(sel)
        test.append((m, int(sel[0])))
        pos.append(set(int(x) for x in sel[1:]))
        train += [(m, int(x)) for x in sel[1:]]
    return dict(train=np.array(train), test=np.array(test), pos=pos, M=M, N=N)


def bpr_init(M, N, Kmax=8, seed=9):
    r = np.random.default_rng(seed)
    return np.round(r.normal(0, 0.1, (M, Kmax)), 6), np.round(r.normal(0, 0.1, (N, Kmax)), 6)


def bpr_eval(P, Q, bi, D):
    """AUC of the held-out positive against all items the user never selected, and hit rate at 10
    (the held-out item ranks in the top 10 among items outside the user's training set)."""
    auc, hit = [], []
    for m, it in D["test"]:
        s = bi + Q @ P[m]
        mask = np.ones(D["N"], bool)
        mask[list(D["pos"][m])] = False
        mask[it] = False
        neg = s[mask]
        auc.append(np.mean(neg < s[it]) + 0.5 * np.mean(neg == s[it]))
        rank = 1 + np.sum(neg > s[it])
        hit.append(rank <= 10)
    return float(np.mean(auc)), float(np.mean(hit))


def bpr_train(D, K, lam, eta, epochs, P0, Q0, loss="logistic", margin=1.0, seed=3):
    """SGD on the BPR objective (22.14): sample a positive pair (u, i) and a negative j (rejection
    sampling from the items outside I_u^+), then ascend log sigma(f(u,i) - f(u,j)) with
    f(u,i) = b_i + p_u' q_i. loss='hinge' uses (22.16) instead. One epoch = |train| steps.
    Returns the factors and the history of (AUC, HR@10) after every epoch (epoch 0 = start)."""
    rng = Mulberry(seed)
    tr = D["train"]
    P = P0[:, :K].copy()
    Q = Q0[:, :K].copy()
    bi = np.zeros(D["N"])
    hist = [bpr_eval(P, Q, bi, D)]
    ntr = len(tr)
    for ep in range(epochs):
        for _ in range(ntr):
            m, i = tr[rng.randint(ntr)]
            while True:
                j = rng.randint(D["N"])
                if j not in D["pos"][m]:
                    break
            x = bi[i] + Q[i] @ P[m] - bi[j] - Q[j] @ P[m]
            if loss == "logistic":
                g = 1.0 / (1.0 + math.exp(x)) if x > -30 else 1.0
            else:
                g = 1.0 if x < margin else 0.0
            pm = P[m].copy()
            P[m] += eta * (g * (Q[i] - Q[j]) - lam * P[m])
            Q[i] += eta * (g * pm - lam * Q[i])
            Q[j] += eta * (-g * pm - lam * Q[j])
            bi[i] += eta * (g - lam * bi[i])
            bi[j] += eta * (-g - lam * bi[j])
        hist.append(bpr_eval(P, Q, bi, D))
    return dict(P=P, Q=Q, bi=bi, hist=np.array(hist))


def popularity_eval(D):
    pop = np.zeros(D["N"])
    for m, i in D["train"]:
        pop[i] += 1
    return bpr_eval(np.zeros((D["M"], 1)), np.zeros((D["N"], 1)), pop, D)


def fm_predict(idx, mu, w, V):
    """Factorisation machine (22.17) for a binary sparse input with active features idx, evaluated
    in O(K |idx|) with the identity (22.18)-(22.20):
        sum_{i<j} v_i'v_j = 1/2 sum_k [ (sum_i v_ik)^2 - sum_i v_ik^2 ]."""
    s = V[idx].sum(0)
    return mu + w[idx].sum() + 0.5 * float(s @ s - (V[idx] ** 2).sum())


def fm_predict_naive(idx, mu, w, V):
    """The same prediction as a double sum over pairs, O(K |idx|^2)."""
    out = mu + w[idx].sum()
    for a in range(len(idx)):
        for b in range(a + 1, len(idx)):
            out += V[idx[a]] @ V[idx[b]]
    return float(out)


def fm_sgd(feats, y, D_in, K, lam, eta, epochs, seed=0):
    """Squared-loss SGD for an FM whose inputs are binary vectors given as lists of active indices."""
    rng = np.random.default_rng(seed)
    mu = float(np.mean(y))
    w = np.zeros(D_in)
    V = rng.normal(0, 0.1, (D_in, K))
    for _ in range(epochs):
        for n in rng.permutation(len(y)):
            idx = feats[n]
            s = V[idx].sum(0)
            f = mu + w[idx].sum() + 0.5 * float(s @ s - (V[idx] ** 2).sum())
            e = y[n] - f
            w[idx] += eta * (e - lam * w[idx])
            V[idx] += eta * (e * (s[None, :] - V[idx]) - lam * V[idx])
    return mu, w, V


def fm_cold_start(D, cold_frac=0.2, K=4, seed=2):
    """Hold out all ratings of some items ("new" items). Compare an id-only FM (= biased MF) with an
    FM that also sees the item genre. Returns warm and cold test RMSE of both."""
    rng = np.random.default_rng(seed)
    M, N = D["R"].shape
    cold = rng.permutation(N)[: int(cold_frac * N)]
    is_cold = np.zeros(N, bool)
    is_cold[cold] = True
    uu, ii = np.nonzero(D["Obs"])
    y = D["R"][uu, ii]
    warm_mask = ~is_cold[ii]
    rs = np.random.default_rng(seed + 1)
    test_w = warm_mask & (rs.random(len(y)) < 0.2)
    train = warm_mask & ~test_w
    test_c = is_cold[ii]
    G = len(GENRES)
    out = {}
    for name, with_genre in (("ids", False), ("ids+genre", True)):
        def feat(a, b):
            f = [a, M + b]
            if with_genre:
                f.append(M + N + D["genre"][b])
            return np.array(f)
        feats = [feat(a, b) for a, b in zip(uu[train], ii[train])]
        mu, w, V = fm_sgd(feats, y[train] - 0.0, M + N + G, K, 0.02, 0.02, 40, seed=0)
        def pr(mask):
            return [fm_predict(feat(a, b), mu, w, V) for a, b in zip(uu[mask], ii[mask])]
        out[name] = (rmse(pr(test_w), y[test_w]), rmse(pr(test_c), y[test_c]))
    out["n_cold_items"] = int(is_cold.sum())
    out["n_cold_test"] = int(test_c.sum())
    return out


# =========================================================================== Section 22.4
def bandit_run(policy, probs, T, seed, eps=0.1):
    """One run of a click bandit with Bernoulli arms probs. The click outcome of arm a at step t is
    1[V[t, a] < p_a] with V drawn from the environment stream (seed), shared by all policies (common
    random numbers); the policy stream is seed + 10**6. Returns the cumulative pseudo-regret
    sum_t (p* - p_{a_t}) after each step, and the number of pulls of each arm."""
    K = len(probs)
    env = Mulberry(seed)
    V = np.array([[env.u() for _ in range(K)] for _ in range(T)])
    pr = Mulberry(seed + 10 ** 6)
    n = np.zeros(K)
    s = np.zeros(K)
    best = max(probs)
    reg = np.zeros(T)
    cum = 0.0
    for t in range(T):
        if t < K and policy != "thompson":
            a = t                                   # play every arm once
        elif policy == "greedy":
            a = int(np.argmax(s / n))
        elif policy == "egreedy":
            if pr.u() < eps:
                a = pr.randint(K)
            else:
                a = int(np.argmax(s / n))
        elif policy == "ucb":
            a = int(np.argmax(s / n + np.sqrt(2.0 * math.log(t + 1) / n)))
        elif policy == "thompson":
            th = [rbeta(pr, 1 + s[k], 1 + n[k] - s[k]) for k in range(K)]
            a = int(np.argmax(th))
        else:
            raise ValueError(policy)
        click = 1.0 if V[t, a] < probs[a] else 0.0
        n[a] += 1
        s[a] += click
        cum += best - probs[a]
        reg[t] = cum
    return reg, n


def rgamma(rng, a):
    """Gamma(a, 1) draw for a >= 1 by the Marsaglia-Tsang squeeze method."""
    d = a - 1.0 / 3.0
    c = 1.0 / math.sqrt(9.0 * d)
    while True:
        while True:
            x = rng.norm()
            v = 1.0 + c * x
            if v > 0:
                break
        v = v * v * v
        u = rng.u()
        if math.log(u) < 0.5 * x * x + d - d * v + d * math.log(v):
            return d * v


def rbeta(rng, a, b):
    x = rgamma(rng, a)
    y = rgamma(rng, b)
    return x / (x + y)


def bandit_curves(probs, T, R, eps, policies=("greedy", "egreedy", "ucb", "thompson"), seed0=100):
    """Average cumulative regret over R runs (seeds seed0 .. seed0+R-1) for each policy, and the share
    of runs in which the best arm received less than half of the pulls."""
    out = {}
    for pol in policies:
        regs, shares = [], []
        for r in range(R):
            reg, n = bandit_run(pol, probs, T, seed0 + r, eps)
            regs.append(reg)
            shares.append(n[int(np.argmax(probs))] / T)
        regs = np.array(regs)
        out[pol] = dict(mean=regs.mean(0), final=float(regs[:, -1].mean()), stuck=float(np.mean(np.array(shares) < 0.5)))
    return out


def ips_experiment(p, e, pi, n, reps, seed=0):
    """Logged data from a policy e (known propensities) used to evaluate a target policy pi.
    Returns the arrays of naive and inverse-propensity estimates of V(pi) = sum_a pi_a p_a."""
    rng = np.random.default_rng(seed)
    K = len(p)
    naive, ips = np.zeros(reps), np.zeros(reps)
    for k in range(reps):
        a = rng.choice(K, size=n, p=e)
        r = (rng.random(n) < p[a]).astype(float)
        naive[k] = r.mean()
        ips[k] = np.mean(r * pi[a] / e[a])
    return naive, ips


# =========================================================================== exports
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    D = simulate_ratings()
    tr, te = split_observed(D)
    M, N = D["R"].shape
    V0 = make_init(N)
    ref = {}
    for K, lam, it, bias in [(0, 5, 20, True), (1, 5, 20, True), (4, 5, 20, True), (8, 0.5, 20, True), (8, 20, 20, True), (4, 5, 20, False), (2, 5, 20, True)]:
        P = als(tr, M, N, K, lam, it, V0, bias, test=te)
        ref["K%d_lam%g_it%d_b%d" % (K, lam, it, bias)] = dict(train=float(P["hist"][-1, 0]), test=float(P["hist"][-1, 1]))
    out = dict(M=M, N=N, train=[tr[0].tolist(), tr[1].tolist(), tr[2].astype(int).tolist()],
               test=[te[0].tolist(), te[1].tolist(), te[2].astype(int).tolist()],
               genre=D["genre"].tolist(), genres=GENRES, V0=V0.tolist(), ref=ref,
               oracle=rmse(D["mean"][te[0], te[1]], te[2]))
    with open(os.path.join(DATA_OUT, "ch22-ratings.json"), "w") as f:
        json.dump(out, f, separators=(",", ":"))
    B = bpr_data()
    P0, Q0 = bpr_init(B["M"], B["N"])
    refb = {}
    for K, lam, eta, ep, loss in [(4, 0.01, 0.05, 15, "logistic"), (1, 0.01, 0.05, 15, "logistic"), (8, 0.0, 0.05, 40, "logistic"), (4, 0.01, 0.05, 15, "hinge")]:
        R = bpr_train(B, K, lam, eta, ep, P0, Q0, loss)
        refb["K%d_lam%g_eta%g_ep%d_%s" % (K, lam, eta, ep, loss)] = dict(auc=float(R["hist"][-1, 0]), hr=float(R["hist"][-1, 1]))
    pa, ph = popularity_eval(B)
    outb = dict(M=B["M"], N=B["N"], train=B["train"].tolist(), test=B["test"].tolist(), P0=P0.tolist(), Q0=Q0.tolist(),
                ref=refb, pop=dict(auc=pa, hr=ph))
    with open(os.path.join(DATA_OUT, "ch22-implicit.json"), "w") as f:
        json.dump(outb, f, separators=(",", ":"))
    return out, outb


# =========================================================================== figures
def _heat(ax, A, mask, vmin=1, vmax=5, cmap="YlGnBu"):
    Z = np.ma.masked_where(~mask, A)
    cm = plt.get_cmap(cmap).copy()
    cm.set_bad("#f1f1f1")
    return ax.imshow(Z, cmap=cm, vmin=vmin, vmax=vmax, aspect="auto", interpolation="nearest")


def fig_22_1(out=None):
    """A small ratings matrix, its bipartite graph, and the similarity of the users."""
    Y = np.array([[1, 1, np.nan, 2, 1],
                  [np.nan, np.nan, 5, np.nan, np.nan],
                  [5, 4, 4, np.nan, 2],
                  [5, 5, np.nan, 5, 1],
                  [np.nan, 2, 3, 4, 3]], float)
    O = ~np.isnan(Y)
    cen = np.where(O, Y - np.nanmean(Y, 1, keepdims=True), 0)
    sim = np.zeros((5, 5))
    for a in range(5):
        for b in range(5):
            co = O[a] & O[b]
            if co.sum() >= 2 and a != b:
                x, y = Y[a, co], Y[b, co]
                sim[a, b] = np.corrcoef(x, y)[0, 1] if x.std() > 0 and y.std() > 0 else np.nan
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.4), gridspec_kw=dict(width_ratios=[1, 1.15]))
    ax = axes[0]
    _heat(ax, np.nan_to_num(Y), O)
    for a in range(5):
        for b in range(5):
            ax.text(b, a, "%d" % Y[a, b] if O[a, b] else "?", ha="center", va="center", fontsize=11,
                    color="white" if O[a, b] and Y[a, b] >= 4 else "black")
    ax.set_xticks(range(5), ["i%d" % (k + 1) for k in range(5)])
    ax.set_yticks(range(5), ["u%d" % (k + 1) for k in range(5)])
    ax.set_title("(a) ratings matrix ($?$ = unobserved)")
    ax = axes[1]
    ax.set_xlim(-0.2, 3.2)
    ax.set_ylim(-0.7, 5.0)
    ax.axis("off")
    ypos_u = {a: 4.4 - a * 0.95 for a in range(5)}
    ypos_i = {b: 4.4 - b * 0.95 for b in range(5)}
    for a in range(5):
        for b in range(5):
            if O[a, b]:
                ax.plot([0.35, 2.65], [ypos_u[a], ypos_i[b]], color=plt.get_cmap("YlGnBu")((Y[a, b] - 1) / 4 * 0.85 + 0.15),
                        lw=0.6 + 0.5 * Y[a, b], alpha=0.9, solid_capstyle="round")
    for a in range(5):
        ax.scatter(0.35, ypos_u[a], s=330, color="white", ec="black", zorder=3)
        ax.text(0.35, ypos_u[a], "u%d" % (a + 1), ha="center", va="center", fontsize=8.5, zorder=4)
        ax.scatter(2.65, ypos_i[a], s=330, color="white", ec="black", zorder=3, marker="s")
        ax.text(2.65, ypos_i[a], "i%d" % (a + 1), ha="center", va="center", fontsize=8.5, zorder=4)
    ax.set_title("(b) the same data as a bipartite graph (width and shade = rating)")
    ax.text(1.5, -0.6, "Pearson sim($u_3,u_4$) = %.2f on co-rated items;  mean rating of $u_1$ = %.1f" % (sim[2, 3], np.nanmean(Y[0])),
            ha="center", fontsize=8.5)
    fig.tight_layout()
    savefig(fig, CH, "fig22-1", out)


def _fit_all(K=4, lam=5.0, iters=25):
    D = simulate_ratings()
    tr, te = split_observed(D)
    M, N = D["R"].shape
    return D, tr, te, M, N


def fig_22_2(out=None):
    """Item embeddings (v_i) of a K = 2 probabilistic matrix factorisation, coloured by genre."""
    D = simulate_ratings()
    M, N = D["R"].shape
    uu, ii = np.nonzero(D["Obs"])
    allobs = (uu, ii, D["R"][uu, ii])
    V0 = make_init(N)
    P = als(allobs, M, N, 2, 3.0, 30, V0)
    Vh = P["V"]
    # rotate to the principal axes (the factors are defined only up to a rotation, gap 22.2)
    Uc, s, Vt = np.linalg.svd(Vh - Vh.mean(0), full_matrices=False)
    Z = (Vh - Vh.mean(0)) @ Vt.T
    fig, ax = plt.subplots(figsize=(5.2, 4.6))
    for g in range(len(GENRES)):
        m = D["genre"] == g
        ax.scatter(Z[m, 0], Z[m, 1], s=26, color=GCOL[g], label=GENRES[g], alpha=0.85, ec="white", lw=0.4)
    ax.axhline(0, color="#bbbbbb", lw=0.7, zorder=0)
    ax.axvline(0, color="#bbbbbb", lw=0.7, zorder=0)
    ax.set_xlabel("first latent axis (principal axis of $v_i$)")
    ax.set_ylabel("second latent axis")
    ax.set_aspect("equal")
    ax.legend(fontsize=8, ncol=2, loc="lower center", bbox_to_anchor=(0.5, 1.0), frameon=False)
    savefig(fig, CH, "fig22-2", out)


def _zero_fill_fragment():
    D = simulate_ratings()
    M, N = D["R"].shape
    uu, ii = np.nonzero(D["Obs"])
    allobs = (uu, ii, D["R"][uu, ii])
    Z = np.clip(svd_zero_fill(allobs, M, N, 10), 1, 5)
    users = np.argsort(-D["Obs"].sum(1))[:22]
    items = np.argsort(-D["Obs"].sum(0))[:26]
    return D, Z, users, items


def fig_22_3(out=None):
    """(a) A fragment of the observed ratings matrix; (b) the predictions of the zero-filled SVD."""
    D, Z, users, items = _zero_fill_fragment()
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.9))
    sub = D["R"][np.ix_(users, items)]
    obs = D["Obs"][np.ix_(users, items)]
    _heat(axes[0], sub, obs)
    axes[0].set_title("(a) observed (grey: unobserved)")
    im = axes[1].imshow(Z[np.ix_(users, items)], cmap="YlGnBu", vmin=1, vmax=5, aspect="auto", interpolation="nearest")
    axes[1].set_title("(b) SVD, $K=10$, clipped to [1, 5]")
    for ax in axes:
        ax.set_xlabel("item (most rated first)")
        ax.set_ylabel("user (most active first)")
        ax.set_xticks([])
        ax.set_yticks([])
    fig.colorbar(im, ax=axes, shrink=0.8, pad=0.02, label="rating")
    savefig(fig, CH, "fig22-3", out)


def fig_22_4(out=None):
    """The top rated items of one user and the top predictions among the items they have not rated."""
    D = simulate_ratings()
    M, N = D["R"].shape
    uu, ii = np.nonzero(D["Obs"])
    allobs = (uu, ii, D["R"][uu, ii])
    P = als(allobs, M, N, 4, 5.0, 30, make_init(N))
    u = int(np.argsort(-D["Obs"].sum(1))[3])
    rated = np.nonzero(D["Obs"][u])[0]
    top_r = rated[np.lexsort((-D["mean"][u, rated], -D["R"][u, rated]))][:10]
    unseen = np.nonzero(~D["Obs"][u])[0]
    pred = mf_predict(P, np.full(len(unseen), u), unseen)
    top_p = unseen[np.argsort(-pred)][:10]
    fig, axes = plt.subplots(1, 2, figsize=(8.8, 3.6))
    for ax, items, vals, ttl in ((axes[0], top_r, D["R"][u, top_r], "(a) top 10 items user %d rated (of %d rated)" % (u, len(rated))),
                                 (axes[1], top_p, np.sort(pred)[::-1][:10], "(b) top 10 predictions (of %d unrated)" % len(unseen))):
        y = np.arange(len(items))[::-1]
        ax.barh(y, vals, color=[GCOL[D["genre"][k]] for k in items], height=0.7)
        ax.set_yticks(y, ["item %d, %s" % (k, GENRES[D["genre"][k]]) for k in items], fontsize=8)
        ax.set_xlim(0, 5.5)
        ax.set_xlabel("rating" if ax is axes[0] else "predicted rating")
        ax.set_title(ttl, fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig22-4", out)
    return u


def fig_22_6(out=None):
    """A design matrix for a factorisation machine: one-hot user, one-hot item, item genre,
    the share of the user's recent ratings by genre, and the target (computed from simulated data)."""
    D = simulate_ratings()
    M, N = D["R"].shape
    rng = np.random.default_rng(3)
    uu, ii = np.nonzero(D["Obs"])
    sel = rng.choice(len(uu), 9, replace=False)
    users = [int(uu[k]) for k in sel]
    items = [int(ii[k]) for k in sel]
    uu_, ii_ = uu[sel], ii[sel]
    nu, ni = 6, 6
    ulist = sorted(set(users))[:nu]
    ilist = sorted(set(items))[:ni]
    X_u = np.array([[1.0 if users[r] == c else 0 for c in ulist] for r in range(9)])
    X_i = np.array([[1.0 if items[r] == c else 0 for c in ilist] for r in range(9)])
    X_g = np.zeros((9, len(GENRES)))
    for r in range(9):
        X_g[r, D["genre"][items[r]]] = 1
    # share of the user's other observed ratings that fall in each genre (normalised, as in the book's figure)
    X_h = np.zeros((9, len(GENRES)))
    for r in range(9):
        o = np.nonzero(D["Obs"][users[r]])[0]
        for g in range(len(GENRES)):
            X_h[r, g] = np.mean(D["genre"][o] == g)
    X_t = np.array([[0.1 * (k % 5 + 1)] for k in range(9)])   # a context feature, here a time of day
    y = D["R"][uu_, ii_][:, None]
    blocks = [(X_u, "user id"), (X_i, "item id"), (X_g, "genre of item"), (X_h, "genres of\nuser's items"), (X_t, "time"), (y, "rating $y$")]
    fig, axes = plt.subplots(1, len(blocks), figsize=(9.2, 3.4), gridspec_kw=dict(width_ratios=[b[0].shape[1] for b in blocks], wspace=0.15))
    for ax, (B, ttl) in zip(axes, blocks):
        ax.imshow(B, cmap="Blues" if ttl != "rating $y$" else "YlGnBu", vmin=0, vmax=1 if ttl != "rating $y$" else 5, aspect="auto", interpolation="nearest")
        ax.set_title(ttl, fontsize=8.5)
        ax.set_xticks([])
        ax.set_yticks(range(9), ["%d" % (r + 1) for r in range(9)] if ax is axes[0] else [])
        ax.tick_params(length=0)
    axes[0].set_ylabel("training case")
    savefig(fig, CH, "fig22-6", out)


def _results_table(D, tr, te):
    M, N = D["R"].shape
    V0 = make_init(N)
    res = {}
    res["global mean"] = rmse(np.full(len(te[2]), tr[2].mean()), te[2])
    P0 = als(tr, M, N, 0, 5.0, 12, V0, True, test=te)
    res["biases only"] = float(P0["hist"][-1, 1])
    res["user-based CF"] = rmse(knn_predict(tr, M, N, list(zip(te[0], te[1]))), te[2])
    Zs = svd_zero_fill(tr, M, N, 8)
    res["SVD, zeros"] = rmse(np.clip(Zs[te[0], te[1]], 1, 5), te[2])
    P = als(tr, M, N, 4, 5.0, 25, V0, True, test=te)
    res["ALS, K=4"] = float(P["hist"][-1, 1])
    return res


def fig_22_S1(out=None):
    """Test RMSE of five predictors (left) and of ALS over a (K, lambda) grid (right)."""
    D = simulate_ratings()
    tr, te = split_observed(D)
    M, N = D["R"].shape
    res = _results_table(D, tr, te)
    V0 = make_init(N)
    Ks = [1, 2, 3, 4, 6, 8]
    lams = [0.5, 1, 2, 5, 10, 20, 50]
    G = np.array([[als(tr, M, N, K, lam, 20, V0, True, test=te)["hist"][-1, 1] for lam in lams] for K in Ks])
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.5), gridspec_kw=dict(width_ratios=[1, 1.1]))
    ax = axes[0]
    names = list(res)
    ax.barh(range(len(names))[::-1], [res[k] for k in names], color=[GREY, GREY, BLUE, ORANGE, GREEN])
    for y, k in zip(range(len(names))[::-1], names):
        ax.text(res[k] + 0.01, y, "%.3f" % res[k], va="center", fontsize=8.5)
    ax.set_yticks(range(len(names))[::-1], names)
    ax.set_xlim(0, max(res.values()) * 1.18)
    ax.set_xlabel("test RMSE")
    ax.set_title("(a) five predictors")
    ax = axes[1]
    im = ax.imshow(G, cmap="viridis_r", aspect="auto", origin="lower")
    ax.set_xticks(range(len(lams)), [("%g" % v) for v in lams])
    ax.set_yticks(range(len(Ks)), [str(k) for k in Ks])
    ax.set_xlabel("$\\lambda$")
    ax.set_ylabel("$K$")
    k0, l0 = np.unravel_index(np.argmin(G), G.shape)
    ax.plot(l0, k0, "r*", ms=11)
    ax.set_title("(b) test RMSE of ALS (best marked)")
    fig.colorbar(im, ax=ax, shrink=0.85)
    fig.tight_layout()
    savefig(fig, CH, "fig22-S1", out)


def fig_22_S2(out=None):
    """ALS against SGD, epoch by epoch (test RMSE)."""
    D = simulate_ratings()
    tr, te = split_observed(D)
    M, N = D["R"].shape
    A = als(tr, M, N, 4, 5.0, 30, make_init(N), True, test=te)
    # SGD with the per-observation penalty lam_sgd corresponds to a per-parameter penalty of about lam_sgd * n_obs/param
    S = sgd_mf(tr, M, N, 4, 0.1, 0.02, 30, seed=0, test=te)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.3))
    axes[0].plot(A["hist"][:, 0], color=BLUE, ls="--", label="ALS train")
    axes[0].plot(A["hist"][:, 1], color=BLUE, label="ALS test")
    axes[0].plot(S["hist"][:, 0], color=ORANGE, ls="--", label="SGD train")
    axes[0].plot(S["hist"][:, 1], color=ORANGE, label="SGD test")
    axes[0].set_ylim(0.3, 1.3)
    axes[0].set_xlabel("epoch / iteration")
    axes[0].set_ylabel("RMSE")
    axes[0].legend(fontsize=8)
    axes[0].set_title("(a) $K=4$: ALS ($\\lambda=5$), SGD ($\\eta=0.02$)")
    objs = []
    V0 = make_init(N)
    for it in range(0, 21):
        P = als(tr, M, N, 4, 5.0, it, V0, True)
        objs.append(objective_522(P, tr, 5.0))
    axes[1].plot(objs, "o-", color=GREEN, ms=3)
    axes[1].set_xlabel("ALS iteration")
    axes[1].set_ylabel("objective (22.5)")
    axes[1].set_title("(b) ALS decreases the objective at every step")
    fig.tight_layout()
    savefig(fig, CH, "fig22-S2", out)


def uniform_split(D, p=0.12, nte=3000, seed=4):
    """Training entries drawn uniformly at random (probability p each), then nte test entries from the rest."""
    rng = np.random.default_rng(seed)
    R = D["R"]
    M, N = R.shape
    mask = rng.random((M, N)) < p
    uu, ii = np.nonzero(mask)
    rest = np.nonzero(~mask)
    k = rng.choice(len(rest[0]), nte, replace=False)
    return (uu, ii, R[uu, ii]), (rest[0][k], rest[1][k], R[rest[0][k], rest[1][k]])


def fig_22_S3(out=None):
    """Zero-filled SVD with and without the 1/p rescaling, against K, when a fraction p of the entries is
    observed uniformly at random (the setting of gap 22.6), compared with ALS."""
    D = simulate_ratings()
    M, N = D["R"].shape
    Ks = list(range(1, 31))
    fig, axes = plt.subplots(1, 2, figsize=(8.6, 3.4), sharey=True)
    for ax, p in zip(axes, (0.12, 0.5)):
        tr, te = uniform_split(D, p)
        r0 = [rmse(np.clip(svd_zero_fill(tr, M, N, K)[te[0], te[1]], 1, 5), te[2]) for K in Ks]
        r1 = [rmse(np.clip(svd_zero_fill(tr, M, N, K, True)[te[0], te[1]], 1, 5), te[2]) for K in Ks]
        als_best = float(als(tr, M, N, 4, 5.0, 25, make_init(N), True, test=te)["hist"][-1, 1])
        ax.plot(Ks, r0, color=ORANGE, label="zeros, as in the book")
        ax.plot(Ks, r1, color=BLUE, label="zeros, divided by $\\hat p$")
        ax.axhline(als_best, color=GREEN, ls="--", label="ALS, $K=4$")
        ax.set_xlabel("$K$")
        ax.set_title("fraction observed $p=%g$" % p, fontsize=10)
        ax.set_ylim(0.4, 3.2)
    axes[0].set_ylabel("test RMSE (clipped to [1, 5])")
    axes[0].legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig22-S3", out)


def mnar_experiment(gamma, seed=11):
    """Observation probability proportional to exp(gamma (r - 3)) times the usual popularity pattern.
    Returns (bias of the observed mean, bias of the IPS mean, RMSE of ALS on all unobserved entries)."""
    D = simulate_ratings()
    R = D["R"]
    M, N = R.shape
    rng = np.random.default_rng(seed)
    w = np.exp(gamma * (R - 3.0))
    P0 = D["P"] * w
    lo, hi = 0.0, 100.0
    for _ in range(60):
        s = 0.5 * (lo + hi)
        if np.minimum(1, s * P0).mean() > 0.12:
            hi = s
        else:
            lo = s
    P = np.minimum(1, lo * P0)
    Obs = rng.random((M, N)) < P
    uu, ii = np.nonzero(Obs)
    y = R[uu, ii]
    truth = R.mean()
    naive = y.mean() - truth
    ips = np.sum(y / P[uu, ii]) / np.sum(1.0 / P[uu, ii]) - truth      # self-normalised
    V0 = make_init(N)
    Pm = als((uu, ii, y), M, N, 4, 5.0, 20, V0)
    pred = Pm["mu"] + Pm["b"][:, None] + Pm["c"][None, :] + Pm["U"] @ Pm["V"].T
    rm = rmse(pred[~Obs], R[~Obs])
    return float(naive), float(ips), rm


def fig_22_S4(out=None):
    """Informative missingness: the bias of the naive mean and the self-normalised IPS mean."""
    gs = [0.0, 0.25, 0.5, 0.75, 1.0]
    rows = [mnar_experiment(g) for g in gs]
    fig, axes = plt.subplots(1, 2, figsize=(8.0, 3.2))
    axes[0].plot(gs, [r[0] for r in rows], "o-", color=RED, label="naive mean of observed")
    axes[0].plot(gs, [r[1] for r in rows], "s-", color=BLUE, label="inverse-propensity (true $p_{ui}$)")
    axes[0].axhline(0, color="k", lw=0.6)
    axes[0].set_xlabel("$\\gamma$ (higher ratings are observed more often)")
    axes[0].set_ylabel("error of the estimated mean rating")
    axes[0].legend(fontsize=8)
    axes[1].plot(gs, [r[2] for r in rows], "o-", color=GREEN)
    axes[1].set_xlabel("$\\gamma$")
    axes[1].set_ylabel("RMSE of ALS on all unobserved entries")
    fig.tight_layout()
    savefig(fig, CH, "fig22-S4", out)


def fig_22_S5(out=None):
    """BPR against the popularity ranking: AUC and hit rate at 10 against the epoch."""
    B = bpr_data()
    P0, Q0 = bpr_init(B["M"], B["N"])
    runs = {"BPR logistic, $K=4$": bpr_train(B, 4, 0.01, 0.05, 25, P0, Q0),
            "BPR hinge, $K=4$": bpr_train(B, 4, 0.01, 0.05, 25, P0, Q0, loss="hinge"),
            "BPR logistic, $K=1$": bpr_train(B, 1, 0.01, 0.05, 25, P0, Q0)}
    pa, ph = popularity_eval(B)
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.3))
    for (name, R), col in zip(runs.items(), (BLUE, ORANGE, GREEN)):
        axes[0].plot(R["hist"][:, 0], color=col, label=name)
        axes[1].plot(R["hist"][:, 1], color=col, label=name)
    axes[0].axhline(pa, color=GREY, ls="--", label="popularity")
    axes[1].axhline(ph, color=GREY, ls="--", label="popularity")
    axes[0].set_ylabel("AUC (held-out item vs. unselected)")
    axes[1].set_ylabel("hit rate at 10")
    for ax in axes:
        ax.set_xlabel("epoch")
    axes[0].legend(fontsize=7.5)
    fig.tight_layout()
    savefig(fig, CH, "fig22-S5", out)


def fig_22_S6(out=None):
    """Cold start: id-only FM against an FM that sees the item genre (warm and cold items)."""
    D = simulate_ratings()
    r = fm_cold_start(D)
    fig, ax = plt.subplots(figsize=(4.6, 3.3))
    x = np.arange(2)
    ax.bar(x - 0.18, [r["ids"][0], r["ids"][1]], 0.36, color=GREY, label="ids only")
    ax.bar(x + 0.18, [r["ids+genre"][0], r["ids+genre"][1]], 0.36, color=BLUE, label="ids + genre")
    for xi, k, dx in ((0, 0, -0.18), (1, 1, -0.18)):
        ax.text(xi + dx, r["ids"][k] + 0.015, "%.3f" % r["ids"][k], ha="center", fontsize=8)
        ax.text(xi + 0.18, r["ids+genre"][k] + 0.015, "%.3f" % r["ids+genre"][k], ha="center", fontsize=8)
    ax.set_xticks(x, ["items seen in training", "new items (cold start)"])
    ax.set_ylabel("test RMSE")
    ax.set_ylim(0, 1.4)
    ax.legend(fontsize=8)
    savefig(fig, CH, "fig22-S6", out)


BANDIT = dict(probs=[0.05, 0.10, 0.12, 0.15, 0.20, 0.30], T=3000, R=60, eps=0.1)


def fig_22_S7(out=None):
    """Average regret of four exploration policies in a six-arm click bandit."""
    c = bandit_curves(BANDIT["probs"], BANDIT["T"], BANDIT["R"], BANDIT["eps"])
    fig, ax = plt.subplots(figsize=(5.4, 3.6))
    for pol, col, lab in (("greedy", RED, "greedy"), ("egreedy", ORANGE, "$\\epsilon$-greedy, $\\epsilon=0.1$"), ("ucb", GREEN, "UCB1"), ("thompson", BLUE, "Thompson sampling")):
        ax.plot(c[pol]["mean"], color=col, label=lab)
    ax.set_xlabel("round $t$")
    ax.set_ylabel("average cumulative regret")
    ax.legend(fontsize=7.5)
    savefig(fig, CH, "fig22-S7", out)


def fig_22_S8(out=None):
    """Sampling distributions of the naive and inverse-propensity estimates of a new policy's click rate."""
    p = np.array([0.1, 0.3, 0.5])
    e = np.array([0.7, 0.2, 0.1])
    pi = np.array([0.1, 0.2, 0.7])
    naive, ips = ips_experiment(p, e, pi, 400, 2000)
    true = float(pi @ p)
    fig, ax = plt.subplots(figsize=(5.2, 3.3))
    bins = np.linspace(0.0, 0.7, 60)
    ax.hist(naive, bins, color=RED, alpha=0.6, label="naive mean of logged clicks")
    ax.hist(ips, bins, color=BLUE, alpha=0.6, label="inverse propensity weighting")
    ax.axvline(true, color="k", ls="--", label="true value %.2f" % true)
    ax.set_xlabel("estimate of the click rate of the new policy")
    ax.set_ylabel("count of 2000 repetitions")
    ax.legend(fontsize=8)
    savefig(fig, CH, "fig22-S8", out)


FIGURES = {
    "22.1": fig_22_1, "22.2": fig_22_2, "22.3": fig_22_3, "22.4": fig_22_4, "22.6": fig_22_6,
    "22.S1": fig_22_S1, "22.S2": fig_22_S2, "22.S3": fig_22_S3, "22.S4": fig_22_S4,
    "22.S5": fig_22_S5, "22.S6": fig_22_S6, "22.S7": fig_22_S7, "22.S8": fig_22_S8,
}

if __name__ == "__main__":
    common.run(FIGURES, CH)
    if "--list" not in sys.argv and "--fig" not in sys.argv:
        export_json()
        print("wrote data/ch22-ratings.json and data/ch22-implicit.json")
