Goal-Space Planning with Subgoal Models, reproduced on FourRooms

Planning cost: value iteration over 104 states vs. over the subgoal graph (Sec. 5.3, 7.3, Fig. 18).

Checks three claims with exact models:
  * goal-space value iteration converges in far fewer sweeps (options jump many steps per backup);
  * the projected values v_g* equal v* when subgoals lie on every optimal route (config "both");
  * the subgoal models are exactly the closed forms r = -(1-gamma^d)/(1-gamma), Gamma = gamma^d.

Fig. 3 / Hypothesis 1: GSP changes the value of more states with the same experience.

One episode under the uniform random policy (reward 0, +1 on entering the goal) is collected once
and replayed, in order, through four learners starting from q = 0. Same data for all four.

Fig. 4 / Hypothesis 2: GSP lets a TD learner learn faster (reward -1 per step).

Paired comparison: run k of every learner uses the same random stream.

Subgoal placement and the region of attraction (Sec. 6.3 remark, App. G.1, Figs. 12, 14 top row, 23).

The four configurations differ only in the hallway next to the goal room. The abstract MDP then knows
only some routes, v_g* encodes "the best route through known subgoals", and an epsilon-greedy learner
is pulled towards that route even when it is not the shortest.

Adapting to change: a lava pool appears on the optimal route (Sec. 6.3, Hypothesis 4, Figs. 13-14).

Setup, following the paper:
  * The learner starts from the optimal action values of the lava-free maze and is then placed in the
    maze with lava on the cells just below the east hallway (each lava cell: reward -20).
  * Only the reward changed, so option policies and Gamma stay fixed. The reward model is represented
    with successor features, r_gamma(s, g) = psi_g(s) . w, and w (one weight per cell entered) is
    re-estimated online by SGD: w[s'] += eta * (R - w[s']). Whenever w moves, Eq. 1-3 are recomputed.
  * Base learner: tabular Sarsa (lambda = 0), alpha = 0.1, epsilon-greedy 0.1.

Initialisation, run both ways:
  * ``paper``:      every learner starts from q*_old, as the paper states.
  * ``consistent``: GSP learners start from q*_old - v_g*_old. A shaped learner's optimum is
                    q* - Phi(s), not q*, so this is the shaped learner's own optimum for the old maze.
With ``paper`` initialisation the shaping term is a non-zero TD error on every step from the start,
so GSP immediately pushes the learner towards the route the abstract MDP prefers. With ``consistent``
initialisation that push is already "paid for" and only *changes* in v_g* produce TD errors. This may explain the paper's App. G.1 puzzle (On Alternate switches fast although v_g* barely moves).

Which potential? v_g* against heuristic and random potentials (Sec. 6.4, Hypothesis 5, Fig. 15; Prop. 5).

Every potential keeps the optimal policy (Ng et al., 1999); they differ in how fast learning gets there.
Prop. 5 says why a good potential helps: with Phi = v*, ONE Bellman backup from q = 0 already yields
the optimal greedy policy.

Shaping versus bootstrapping from v_g* (Sec. 6.5 "approximate LAVI", Fig. 16; App. F; robustness, Sec. 6.2).

Bootstrapping straight from v_g* (beta = 1) inherits every error in v_g*; potential-based shaping cannot
change the optimal policy whatever v_g* is. The base learner here is one-step Sarsa (lambda = 0): a target
that bootstraps from a fixed function is a one-step target, and combining it with eligibility traces is a
mismatch (the trace sum no longer telescopes to a lambda-return). Panel (a) adds that combination, as the
paper's Sarsa(lambda) setting would have it, to show the effect. Three views:
  (a) exact, correct v_g* (config "both"):         bootstrapping is fine, even fast;
  (b) exact but biased v_g* (config "on_alternate"): bootstrapping locks onto the 19-step route;
  (c) noisy option models (multiplicative noise on r_gamma and Gamma, as learned models would have):
      shaping degrades gracefully, bootstrapping does not.

What planning computation buys: Dyna-Q with n planning updates per step versus GSP (Sec. 7.2-7.3, Fig. 17).

The paper's Fig. 17 is explicitly hypothetical. This puts measured points on it for the tabular case:
Dyna-Q's learning speed as a function of planning updates per real step, against GSP (on the same
Q-learning base learner), whose planning is a one-off goal-space value iteration.