"""Code of the notebook hikeFA.ipynb (the discounted windy hike: model, simulator, exact planning,
feature classes, least-squares / interpolation / neural-network fits, approximate value iteration,
fitted Q iteration, policy gradient tools, plots), shared by Baseline.py, Correction.py,
evaluator.py and Correction.ipynb.

The evaluator injects everything defined here into the namespace of each student file before
running it, so that a submission may freely use the functions and classes of the notebook
(Hike, Simulator, hatFeatures, LeastSquares, approximateValueIteration, MLP, ...) without
copying them.
"""

from collections import deque

import numpy as np
import matplotlib.pyplot as plt


# ----------------------------------------------------------------------------
# The environment
# ----------------------------------------------------------------------------
class Hike:
    """The discounted windy hike.

    Grid of width x height cells; entry at (0, 0) (bottom-left), bar at (width-1, 0) (bottom-right);
    pits = rectangles [x0, x1) x [y0, y1) (a list of tuples, or a single tuple). At each step the
    hiker chooses a direction (0: right, 1: up, 2: left, 3: down); the move is the chosen one with
    probability 1 - 3 wind, and each of the 3 other directions with probability wind. A move
    towards the border leaves the hiker in place. The bar is absorbing with reward 1 for every step
    that ends in it; falling into a pit leads to the absorbing *sink* state (reward 0 forever).
    The criterion is the discounted return sum_t gamma^t R_t.

    States: the cells outside the pits, numbered 0, ..., nbStates - 2 (column by column), plus the
    sink nbStates - 1. A deterministic policy is an integer array of size nbStates; a stochastic
    one an array (nbStates, 4) of probabilities. Values V are arrays of size nbStates, Q-functions
    arrays (nbStates, 4). Everything below is exact (sums over the 4 possible moves)."""

    moveDirections = [(1, 0), (0, 1), (-1, 0), (0, -1)]  # right, up, left, down

    def __init__(self, width=30, height=15, pits=((9, 21, 2, 6),), wind=0.05, gamma=0.95):
        if len(pits) == 4 and np.isscalar(pits[0]):
            pits = (tuple(pits),)
        self.width, self.height, self.pits, self.wind, self.gamma = width, height, [tuple(p) for p in pits], wind, gamma
        self.cells = [(i, j) for i in range(width) for j in range(height) if not self.inPit((i, j))]
        self.index = {c: k for k, c in enumerate(self.cells)}
        self.nbStates = len(self.cells) + 1
        self.nbActions = 4
        self.sink = self.nbStates - 1
        self.start = self.index[(0, 0)]
        self.bar = self.index[(width - 1, 0)]
        self.Vmax = 1 / (1 - gamma)
        # positions of the states (the sink at (-1, -1)) and normalized coordinates in [0, 1]^2 (the sink at (0, 0))
        self.positions = np.array(self.cells + [(-1, -1)], dtype=float)
        self.xy = self.positions / [max(width - 1, 1), max(height - 1, 1)]
        self.xy[self.sink] = 0.0
        self.isSink = np.arange(self.nbStates) == self.sink
        # successors: succ[s, b] = state reached from s when the actual move is b
        self.succ = np.array([[self.nextState(s, b) for b in range(4)] for s in range(self.nbStates)])
        # probs[a, b] = probability that the actual move is b when the chosen direction is a
        self.probs = np.full((4, 4), wind)
        np.fill_diagonal(self.probs, 1 - 3 * wind)
        self.rewardOfState = np.zeros(self.nbStates)   # reward of a step *ending* in that state
        self.rewardOfState[self.bar] = 1.0
        self.r = self.rewardOfState[self.succ] @ self.probs.T   # r[s, a] = expected reward of (s, a)

    # ---- geometry ----
    def inPit(self, pos):
        return any(x0 <= pos[0] < x1 and y0 <= pos[1] < y1 for (x0, x1, y0, y1) in self.pits)

    def pos2state(self, pos):
        """State of a position (i, j): the sink for a position in a pit, -1 outside the grid."""
        pos = (int(pos[0]), int(pos[1]))
        if pos in self.index:
            return self.index[pos]
        if 0 <= pos[0] < self.width and 0 <= pos[1] < self.height:
            return self.sink
        return -1

    def state2pos(self, s):
        return self.cells[s] if s < self.sink else (-1, -1)

    def nextState(self, s, b):
        if s == self.sink or s == self.bar:
            return s
        i, j = self.cells[s]
        m = self.moveDirections[b]
        ns = self.pos2state((i + m[0], j + m[1]))
        return s if ns < 0 else ns

    def distanceToBar(self):
        """Shortest number of moves from each state to the bar, avoiding the pits (inf for the sink)."""
        inv = [[] for _ in range(self.nbStates)]
        for s in range(self.nbStates):
            for b in range(4):
                inv[self.succ[s, b]].append(s)
        d = np.full(self.nbStates, np.inf)
        d[self.bar] = 0
        queue = deque([self.bar])
        while queue:
            s = queue.popleft()
            for s2 in inv[s]:
                if d[s2] == np.inf and s2 != self.sink:
                    d[s2] = d[s] + 1
                    queue.append(s2)
        return d

    # ---- the model: exact backups ----
    def backup(self, V):
        """Exact Bellman backup Q[s, a] = r(s, a) + gamma E[V(S') | s, a], for every state and action."""
        return self.r + self.gamma * (V[self.succ] @ self.probs.T)

    def T(self, V):
        """Bellman optimality operator: (T V)(s) = max_a backup."""
        return self.backup(V).max(axis=1)

    def greedy(self, V):
        """Greedy policy of V (ties: smallest action index)."""
        return self.backup(V).argmax(axis=1)

    def policyProbs(self, pi):
        """Stochastic form (nbStates, 4) of a policy given as an integer array or as probabilities."""
        pi = np.asarray(pi)
        return pi if pi.ndim == 2 else np.eye(4)[pi]

    def Tpi(self, V, pi):
        """Bellman operator of the policy pi."""
        return (self.policyProbs(pi) * self.backup(V)).sum(axis=1)

    def valueIteration(self, tol=1e-9, maxIter=100000):
        """Exact optimal value, by value iteration up to precision tol (sup norm)."""
        V = np.zeros(self.nbStates)
        for k in range(maxIter):
            nV = self.T(V)
            if np.abs(nV - V).max() < tol * (1 - self.gamma) / self.gamma:
                return nV
            V = nV
        return V

    def policyValue(self, pi, tol=1e-10):
        """Exact value of a policy (iterating T^pi, which is cheap: 4 successors per state)."""
        P = self.policyProbs(pi) @ self.probs      # P[s, b] = probability of the actual move b
        rpi = (self.policyProbs(pi) * self.r).sum(axis=1)
        V = np.zeros(self.nbStates)
        for k in range(100000):
            nV = rpi + self.gamma * (V[self.succ] * P).sum(axis=1)
            if np.abs(nV - V).max() < tol:
                return nV
            V = nV
        return V

    def occupation(self, pi, mu=None):
        """Discounted occupation measure of pi from the initial law mu (default: the entry),
        normalized by (1 - gamma): d(s) = (1 - gamma) sum_t gamma^t P(S_t = s)."""
        if mu is None:
            mu = np.zeros(self.nbStates)
            mu[self.start] = 1.0
        P = self.policyProbs(pi) @ self.probs
        d, m = mu.astype(float).copy(), mu.astype(float).copy()
        for t in range(100000):
            nm = np.zeros(self.nbStates)
            for b in range(4):
                np.add.at(nm, self.succ[:, b], self.gamma * m * P[:, b])
            d += nm
            m = nm
            if m.sum() < 1e-13:
                break
        return (1 - self.gamma) * d

    def lookaheadPolicy(self, V, k=1):
        """k-step lookahead policy: greedy with respect to T^(k-1) V."""
        W = V.copy()
        for _ in range(k - 1):
            W = self.T(W)
        return self.greedy(W)

    # ---- the simulator ----
    def step(self, s, a):
        """One transition from each state s[i] with action a[i] (integer arrays): returns (rewards, next states)."""
        s, a = np.asarray(s), np.asarray(a)
        u = np.random.random(s.shape)
        b = np.where(u < 1 - 3 * self.wind, a, np.random.randint(0, 4, s.shape))
        ns = self.succ[s, b]
        return self.rewardOfState[ns], ns

    def simulator(self, budget=None):
        return Simulator(self, budget)

    # ---- plots ----
    def image(self, V):
        """Array (height, width) of the values of the cells (nan in the pits), for plt.imshow."""
        img = np.full((self.height, self.width), np.nan)
        for s, (i, j) in enumerate(self.cells):
            img[j, i] = V[s]
        return img

    def plotValue(self, V, title="", ax=None, colorbar=True, **kwargs):
        ax = ax or plt.gca()
        im = ax.imshow(self.image(np.asarray(V, dtype=float)), origin="lower", **kwargs)
        ax.set_title(title)
        ax.set_xticks([])
        ax.set_yticks([])
        if colorbar:
            plt.colorbar(im, ax=ax, fraction=0.025)
        return im

    def plotPolicy(self, pi, ax=None, title="", color="white", **kwargs):
        """Arrows of a deterministic policy (on top of the current image)."""
        ax = ax or plt.gca()
        pi = np.asarray(pi)
        for s, (i, j) in enumerate(self.cells):
            if s == self.bar:
                continue
            m = self.moveDirections[int(pi[s])]
            ax.arrow(i - 0.3 * m[0], j - 0.3 * m[1], 0.5 * m[0], 0.5 * m[1], head_width=0.25, head_length=0.2,
                     length_includes_head=True, color=color, **kwargs)
        if title:
            ax.set_title(title)
        ax.set_xticks([])
        ax.set_yticks([])


class Simulator:
    """What a model-free algorithm is allowed to see of a hike: the state space (nbStates, the sink,
    the entry, the normalized coordinates xy of the states), gamma, nbActions, and transitions
    step(s, a) -> (rewards, next states) for any arrays of states and actions. The transition
    probabilities and the reward function are hidden. nbCalls counts the simulated transitions;
    if a budget is given, step refuses to exceed it."""

    def __init__(self, hike, budget=None):
        self._hike = hike
        self.gamma, self.nbStates, self.nbActions = hike.gamma, hike.nbStates, hike.nbActions
        self.sink, self.start, self.bar = hike.sink, hike.start, hike.bar
        self.width, self.height = hike.width, hike.height
        self.xy, self.positions, self.isSink = hike.xy, hike.positions, hike.isSink
        self.cells, self.pos2state, self.state2pos = hike.cells, hike.pos2state, hike.state2pos  # the state space is known
        self.image, self.plotValue, self.plotPolicy = hike.image, hike.plotValue, hike.plotPolicy
        self.budget = budget
        self.nbCalls = 0

    def step(self, s, a):
        n = np.size(s)
        if self.budget is not None and self.nbCalls + n > self.budget:
            raise RuntimeError("simulation budget exceeded (%d transitions allowed, %d used)" % (self.budget, self.nbCalls))
        self.nbCalls += n
        return self._hike.step(s, a)


def loss(hike, pi, Vstar=None):
    """Loss V* - V^pi of a policy (array over the states), exact."""
    if Vstar is None:
        Vstar = hike.valueIteration()
    return Vstar - hike.policyValue(pi)


# ----------------------------------------------------------------------------
# Feature classes: each function returns a matrix Phi (nbStates, d), V(s) = Phi[s] . theta.
# The sink always has its own feature (first column) and no other: its value is fitted exactly.
# ----------------------------------------------------------------------------
def blockFeatures(hike, c):
    """Indicators of c x c blocks of cells (state aggregation): least squares on this class = block averages."""
    i, j = hike.positions[:, 0], hike.positions[:, 1]
    block = (i // c) * ((hike.height + c - 1) // c) + j // c
    block[hike.sink] = -1
    ids = np.unique(block)
    Phi = (block[:, None] == ids[None, :]).astype(float)
    return Phi


def hatFeatures(hike, kx, ky=None):
    """Two-dimensional hat functions (bilinear interpolation) on a grid of knots every kx cells
    horizontally and ky vertically (knots in the pits are dropped, the weights are renormalized).
    Returns (Phi, knots): knots[k] is the state at which the k-th feature equals 1 (the sink for k = 0),
    so that V(knots) = theta: the class interpolates the values at the knots."""
    ky = kx if ky is None else ky
    i, j = hike.positions[:, 0], hike.positions[:, 1]
    xs = np.unique(np.append(np.arange(0, hike.width, kx), hike.width - 1))
    ys = np.unique(np.append(np.arange(0, hike.height, ky), hike.height - 1))

    def hat(t, knots):
        out = np.zeros((len(t), len(knots)))
        for k in range(len(knots)):
            lo = knots[k - 1] if k > 0 else knots[k] - 1
            hi = knots[k + 1] if k < len(knots) - 1 else knots[k] + 1
            out[:, k] = np.clip(np.where(t < knots[k], (t - lo) / (knots[k] - lo), (hi - t) / (hi - knots[k])), 0, 1)
        return out

    Phi = (hat(i, xs)[:, :, None] * hat(j, ys)[:, None, :]).reshape(hike.nbStates, -1)
    knots = np.array([hike.pos2state((x, y)) for x in xs for y in ys])
    keep = knots != hike.sink
    Phi, knots = Phi[:, keep], knots[keep]
    Phi = Phi / np.maximum(Phi.sum(axis=1, keepdims=True), 1e-12)
    Phi[hike.sink] = 0
    return np.column_stack([hike.isSink.astype(float), Phi]), np.concatenate([[hike.sink], knots])


def polynomialFeatures(hike, degree):
    """Monomials x^a y^b, a + b <= degree, of the normalized coordinates."""
    x, y = hike.xy[:, 0], hike.xy[:, 1]
    Phi = np.column_stack([x ** a * y ** b for a in range(degree + 1) for b in range(degree + 1 - a)])
    Phi[hike.sink] = 0
    return np.column_stack([hike.isSink.astype(float), Phi])


def rbfFeatures(hike, nx, ny, width=1.0):
    """A constant and nx x ny Gaussian bumps centered on a grid, of standard deviation `width` times the spacing."""
    x, y = hike.xy[:, 0], hike.xy[:, 1]
    cx, cy = np.meshgrid(np.linspace(0, 1, nx), np.linspace(0, 1, ny))
    cx, cy = cx.ravel(), cy.ravel()
    Phi = np.exp(-((x[:, None] - cx) ** 2 * (nx - 1) ** 2 + (y[:, None] - cy) ** 2 * (ny - 1) ** 2) / (2 * width ** 2))
    Phi[hike.sink] = 0
    return np.column_stack([hike.isSink.astype(float), 1.0 - hike.isSink, Phi])


# ----------------------------------------------------------------------------
# Representations of a value or Q function with few parameters, and how to fit them
# ----------------------------------------------------------------------------
class LinearFunction:
    """V = Phi theta (theta of size d) or Q = Phi theta^T (theta of shape (nbActions, d))."""

    def __init__(self, Phi, theta):
        self.Phi, self.theta = Phi, np.asarray(theta, dtype=float)

    def values(self):
        return self.Phi @ self.theta if self.theta.ndim == 1 else self.Phi @ self.theta.T

    def nbParameters(self):
        return self.theta.size


class LeastSquares:
    """Weighted least-squares fit on the class Phi: fit(Y) returns the theta minimizing
    sum_s mu(s) (Phi[s] theta - Y[s])^2 (mu uniform by default; minimal norm if underdetermined)."""

    def __init__(self, Phi, mu=None):
        self.Phi = Phi
        w = np.ones(Phi.shape[0]) if mu is None else np.sqrt(np.maximum(np.asarray(mu, dtype=float), 0))
        self.w = w
        self.pinv = np.linalg.pinv(Phi * w[:, None])

    def fit(self, Y):
        return self.pinv @ (Y * self.w)


class Interpolation:
    """Fit by interpolation at the knots of a hat basis: theta = Y[knots] (an averager)."""

    def __init__(self, Phi, knots):
        self.Phi, self.knots = Phi, knots

    def fit(self, Y):
        return Y[self.knots]


def approximateValueIteration(hike, Phi, fitter, nIter=2000, tol=1e-7, V0=None):
    """V_{k+1} = fit(T V_k) with the exact backup T of the model. Returns (LinearFunction, history of
    the sup-norm changes). Stops at precision tol, or when the iterates blow up (divergence)."""
    theta = fitter.fit(np.zeros(hike.nbStates) if V0 is None else V0)
    history = []
    for k in range(nIter):
        newTheta = fitter.fit(hike.T(Phi @ theta))
        change = np.abs(Phi @ (newTheta - theta)).max()
        history.append(change)
        theta = newTheta
        if change < tol or change > 1e6 or not np.isfinite(change):
            break
    return LinearFunction(Phi, theta), np.array(history)


class MLP:
    """A one-hidden-layer network (ReLU) in numpy, trained by Adam on the squared error.

    inputs: an array (nbStates, nInputs) of the inputs of all the states (e.g. hike.xy or
    np.column_stack([hike.xy, hike.isSink])), so that values() returns the outputs for every state:
    a value function if nOutputs = 1, a Q-function if nOutputs = nbActions."""

    def __init__(self, inputs, nHidden=32, nOutputs=1, seed=None):
        rng = np.random.default_rng(seed)
        self.inputs = np.asarray(inputs, dtype=float)
        nInputs = self.inputs.shape[1]
        self.W1 = rng.normal(0, 1 / np.sqrt(nInputs), (nInputs, nHidden))
        self.b1 = np.zeros(nHidden)
        self.W2 = rng.normal(0, 1 / np.sqrt(nHidden), (nHidden, nOutputs))
        self.b2 = np.zeros(nOutputs)
        self.parameters = [self.W1, self.b1, self.W2, self.b2]
        self.m = [np.zeros_like(p) for p in self.parameters]
        self.v = [np.zeros_like(p) for p in self.parameters]
        self.t = 0

    def nbParameters(self):
        return sum(p.size for p in self.parameters)

    def forward(self, X):
        self._X = X
        self._Z = X @ self.W1 + self.b1
        self._H = np.maximum(self._Z, 0)
        return self._H @ self.W2 + self.b2

    def backward(self, dOut):
        """Gradients of sum(output * dOut) with respect to the parameters, after a forward pass."""
        gW2 = self._H.T @ dOut
        gb2 = dOut.sum(axis=0)
        dH = (dOut @ self.W2.T) * (self._Z > 0)
        return [self._X.T @ dH, dH.sum(axis=0), gW2, gb2]

    def adamStep(self, grads, lr=1e-3, beta1=0.9, beta2=0.999, eps=1e-8):
        self.t += 1
        for p, g, m, v in zip(self.parameters, grads, self.m, self.v):
            m *= beta1
            m += (1 - beta1) * g
            v *= beta2
            v += (1 - beta2) * g * g
            p -= lr * (m / (1 - beta1 ** self.t)) / (np.sqrt(v / (1 - beta2 ** self.t)) + eps)

    def fit(self, X, Y, actions=None, epochs=1, batchSize=128, lr=1e-3):
        """Stochastic gradient steps on the mean squared error between the outputs (the output of the
        action actions[i] when given) and the targets Y; returns the loss of the last epoch."""
        n = len(Y)
        for e in range(epochs):
            order = np.random.permutation(n)
            total = 0.0
            for i0 in range(0, n, batchSize):
                idx = order[i0:i0 + batchSize]
                out = self.forward(X[idx])
                if actions is None:
                    err = out[:, 0] - Y[idx]
                    dOut = (2 * err / len(idx))[:, None]
                else:
                    err = out[np.arange(len(idx)), actions[idx]] - Y[idx]
                    dOut = np.zeros_like(out)
                    dOut[np.arange(len(idx)), actions[idx]] = 2 * err / len(idx)
                total += (err ** 2).sum()
                self.adamStep(self.backward(dOut), lr)
        return total / n

    def values(self):
        out = self.forward(self.inputs)
        return out[:, 0] if out.shape[1] == 1 else out


# ----------------------------------------------------------------------------
# Fitted Q iteration from a simulator
# ----------------------------------------------------------------------------
def uniformBatch(simulator, n):
    """n transitions (s, a, r, s') with s uniform on the cells and a uniform."""
    s = np.random.randint(0, simulator.nbStates - 1, n)
    a = np.random.randint(0, simulator.nbActions, n)
    r, ns = simulator.step(s, a)
    return s, a, r, ns


def trajectoryBatch(simulator, policy, n, startStates=None, maxLength=100):
    """n transitions collected along episodes of a stochastic policy (array (nbStates, 4)), started at
    a state drawn from startStates (default: the entry), truncated at maxLength steps or when the
    bar or the sink is reached (nothing happens there any more)."""
    policy = np.asarray(policy)
    if policy.ndim == 1:
        policy = np.eye(4)[policy]
    startStates = np.array([simulator.start]) if startStates is None else np.asarray(startStates)
    S, A, R, NS = [], [], [], []
    count = 0
    while count < n:
        m = min(64, n - count)
        s = np.random.choice(startStates, m)
        for t in range(maxLength):
            s = s[:n - count]  # never more than n transitions in total
            cum = policy[s].cumsum(axis=1)
            a = (np.random.random(len(s))[:, None] < cum).argmax(axis=1)
            r, ns = simulator.step(s, a)
            S.append(s), A.append(a), R.append(r), NS.append(ns)
            count += len(s)
            alive = (ns != simulator.sink) & (ns != simulator.bar)
            s = ns[alive]
            if len(s) == 0 or count >= n:
                break
    return tuple(np.concatenate(x)[:n] for x in (S, A, R, NS))


def fittedQIteration(simulator, Phi, fitters, nIter=300, n=None, batch=None, tol=1e-7):
    """Fitted Q iteration with a linear class per action: Q(s, a) = Phi[s] . theta[a].
    Either a fixed batch (s, a, r, s') is given, or n fresh uniform transitions are drawn at every
    iteration. fitters[a] is an object with a method fit(X, Y) -> theta (see perActionLeastSquares).
    Returns (LinearFunction with theta of shape (4, d), history of the changes)."""
    d = Phi.shape[1]
    theta = np.zeros((simulator.nbActions, d))
    history = []
    if batch is not None:
        s, a, r, ns = batch
    for k in range(nIter):
        if batch is None:
            s, a, r, ns = uniformBatch(simulator, n)
        Y = r + simulator.gamma * (Phi[ns] @ theta.T).max(axis=1)
        newTheta = np.array([fitters[b].fit(s[a == b], Y[a == b]) for b in range(simulator.nbActions)])
        change = np.abs(Phi @ (newTheta - theta).T).max()
        history.append(change)
        theta = newTheta
        if (batch is not None and change < tol) or change > 1e6 or not np.isfinite(change):
            break
    return LinearFunction(Phi, theta), np.array(history)


class SampleLeastSquares:
    """fit(states, Y): least squares of the targets Y on the features Phi[states] (for fittedQIteration).
    The pseudo-inverse is cached, so that iterating on a fixed batch costs one matrix product."""

    def __init__(self, Phi):
        self.Phi = Phi
        self._cache = (None, None)

    def fit(self, states, Y):
        if len(states) == 0:
            return np.zeros(self.Phi.shape[1])
        key = (len(states), int(states[0]), int(states[-1]), int(states.sum()))
        if self._cache[0] != key:
            self._cache = (key, np.linalg.pinv(self.Phi[states]))
        return self._cache[1] @ Y


class SampleAverages:
    """fit(states, Y): the targets are averaged over the samples of each knot of a hat basis (an
    averager: the samples must be drawn at the knots). Knots without a sample keep the value 0."""

    def __init__(self, Phi, knots):
        self.Phi, self.knots = Phi, knots
        self.lookup = -np.ones(Phi.shape[0], dtype=int)
        self.lookup[knots] = np.arange(len(knots))

    def fit(self, states, Y):
        k = self.lookup[states]
        theta = np.zeros(len(self.knots))
        count = np.bincount(k, minlength=len(self.knots))
        np.add.at(theta, k, Y)
        return theta / np.maximum(count, 1)


def knotBatch(simulator, knots, m):
    """m transitions from every knot (except the sink) and every action: the data of an averager."""
    kn = np.asarray(knots)
    kn = kn[kn != simulator.sink]
    s = np.repeat(kn, simulator.nbActions * m)
    a = np.tile(np.repeat(np.arange(simulator.nbActions), m), len(kn))
    r, ns = simulator.step(s, a)
    return s, a, r, ns


def fittedQNetwork(simulator, net, batch, nIter=100, epochs=2, batchSize=128, lr=3e-3, targetNetwork=True, callback=None):
    """Fitted Q iteration with a neural network Q(s, .) = net(inputs[s]) (nOutputs = nbActions) on a
    fixed batch (s, a, r, s'): nIter times, compute the targets r + gamma max_a' Q(s', a') and fit
    them by `epochs` epochs of Adam. With targetNetwork=False the targets are recomputed from the
    current network before every minibatch (semi-gradient TD, no frozen target)."""
    s, a, r, ns = batch
    X, Xn = net.inputs[s], net.inputs[ns]
    n = len(s)
    for k in range(nIter):
        if targetNetwork:
            Y = r + simulator.gamma * net.forward(Xn).max(axis=1)
            net.fit(X, Y, a, epochs=epochs, batchSize=batchSize, lr=lr)
        else:
            for e in range(epochs):
                order = np.random.permutation(n)
                for i0 in range(0, n, batchSize):
                    idx = order[i0:i0 + batchSize]
                    Y = r[idx] + simulator.gamma * net.forward(Xn[idx]).max(axis=1)
                    out = net.forward(X[idx])
                    dOut = np.zeros_like(out)
                    dOut[np.arange(len(idx)), a[idx]] = 2 * (out[np.arange(len(idx)), a[idx]] - Y) / len(idx)
                    net.adamStep(net.backward(dOut), lr)
        if callback is not None:
            callback(k, net)
    return net



# ----------------------------------------------------------------------------
# Comparing an approximate value with the exact one
# ----------------------------------------------------------------------------
def summary(hike, V, Vstar, policy=None):
    """Errors of an approximate value V (array over the states): sup |V - V*| over the cells, the
    Bellman residual sup |T V - V| and the a posteriori bound residual / (1 - gamma), and the loss
    V* - V^pi of the policy (default: greedy for V), at the entry and on average over the cells."""
    V = np.asarray(V, dtype=float)
    pi = hike.greedy(V) if policy is None else policy
    L = Vstar - hike.policyValue(pi)
    res = np.abs(hike.T(V) - V)[:-1].max() if np.all(np.isfinite(V)) else np.inf
    return dict(supError=np.abs(V - Vstar)[:-1].max() if np.all(np.isfinite(V)) else np.inf, residual=res,
                bound=res / (1 - hike.gamma), lossAtEntry=L[hike.start], meanLoss=L[:-1].mean(), maxLoss=L[:-1].max(), policy=pi, loss=L)


def report(hike, name, V, Vstar, policy=None):
    s = summary(hike, V, Vstar, policy)
    print("%-45s sup error %8.3f   residual %7.3f (bound %7.2f)   loss at the entry %7.4f   mean loss %7.4f   max loss %7.4f"
          % (name, s["supError"], s["residual"], s["bound"], s["lossAtEntry"], s["meanLoss"], s["maxLoss"]))
    return s


def plotFit(hike, V, Vstar, title="", policy=None, figsize=(15, 3)):
    """Three pictures: the approximate value, its error |V - V*|, and the loss of its greedy policy."""
    s = summary(hike, V, Vstar, policy)
    fig, axes = plt.subplots(1, 3, figsize=figsize)
    hike.plotValue(np.clip(V, -hike.Vmax, 2 * hike.Vmax), title, axes[0])
    hike.plotValue(np.abs(V - Vstar), "|V - V*|  (sup %.2f)" % s["supError"], axes[1])
    hike.plotValue(s["loss"], "loss of the policy  (mean %.3f)" % s["meanLoss"], axes[2])
    hike.plotPolicy(s["policy"], axes[2], color="white", alpha=0.5)
    plt.tight_layout()
    return s

# ----------------------------------------------------------------------------
# Policy gradient (tabular softmax policies, discounted criterion)
# ----------------------------------------------------------------------------
def softmax(theta):
    e = np.exp(theta - theta.max(axis=1, keepdims=True))
    return e / e.sum(axis=1, keepdims=True)


def exactPolicyGradient(hike, theta, mu):
    """J(theta) = V^pi(mu) and its exact gradient for the tabular softmax pi = softmax(theta),
    from the model: d J / d theta(s, a) = d(s) pi(a | s) A(s, a) / (1 - gamma), with d the occupation
    measure from mu and A the advantage. Returns (J, gradient, advantage, occupation)."""
    pi = softmax(theta)
    V = hike.policyValue(pi)
    A = hike.backup(V) - V[:, None]
    d = hike.occupation(pi, mu)
    return mu @ V, d[:, None] * pi * A / (1 - hike.gamma), A, d


def episodes(simulator, theta, N, length, startStates=None):
    """N episodes of `length` steps of the softmax policy, started at states drawn from startStates
    (default: the entry). Returns the arrays S, A, R of shape (length, N)."""
    pi = softmax(theta)
    startStates = np.array([simulator.start]) if startStates is None else np.asarray(startStates)
    s = np.random.choice(startStates, N)
    S, A, R = np.zeros((length, N), int), np.zeros((length, N), int), np.zeros((length, N))
    for t in range(length):
        a = (np.random.random(N)[:, None] < pi[s].cumsum(axis=1)).argmax(axis=1)
        r, ns = simulator.step(s, a)
        S[t], A[t], R[t] = s, a, r
        s = ns
    return S, A, R


def reinforceGradient(simulator, theta, S, A, R, baseline=True, discountScores=True):
    """REINFORCE estimate of the gradient from episodes (S, A, R): sum over t of gamma^t * score(A_t | S_t)
    * (reward-to-go - baseline), the baseline being the average reward-to-go at time t over the
    episodes. Returns the gradient (nbStates, 4) and the mean discounted return."""
    pi = softmax(theta)
    length, N = R.shape
    gamma = simulator.gamma
    toGo = np.zeros_like(R)
    acc = np.zeros(N)
    for t in range(length - 1, -1, -1):
        acc = R[t] + gamma * acc
        toGo[t] = acc
    b = toGo.mean(axis=1, keepdims=True) if baseline else 0.0
    g = np.zeros_like(theta)
    for t in range(length):
        w = (gamma ** t if discountScores else 1.0) * (toGo[t] - (b[t] if baseline else 0.0)) / N
        np.add.at(g, (S[t], A[t]), w)
        g[S[t]] -= w[:, None] * pi[S[t]]
    return g, toGo[0].mean()
