What if the edge you choose isn't the edge you get?
Topic 08 solved the shortest path under a quiet assumption: choosing an edge means taking it. Topic 20 removes that assumption on the same network, and topic 22 removes the assumption that the numbers are known before you commit; the two honest ways to cope (average over what might happen, or armour against the worst of it) give different answers on the same problem. Topic 09 is the mathematics of waiting when arrivals and service are random.
Topic 08's whole method rested on one quiet assumption: pick the cheapest edge out of a node, and you get that edge. A Markov decision process (MDP) is what is left of the shortest-path problem once that assumption is removed. You still choose an action at every state. The world still responds with a reward and a next state. But the next state is now drawn from a probability distribution over what your action makes likely, not a guarantee of what it makes certain, and "Markov" is the name for the specific, useful restriction that this distribution depends only on the current state and action, never on the path taken to reach them.
This is exactly the gap topic 08 named on its way out the door: the same recursion, "with an expectation where the min is." Where topic 08 asked which edge is cheapest, an MDP asks which action has the best cheapest-in-expectation outcome, averaged honestly over everything that action might actually cause.
Solving an MDP still assumes you are handed the model. Every transition probability, every reward, known in advance, exactly like topic 08's road network was simply given. Reinforcement learning (RL) is what happens when that assumption goes too: no one hands you the probabilities or the rewards. You are dropped at S with nothing but the ability to try an action, observe what state you land in and what reward you got, and try again. The "R" in RL is the same reward as the Bellman equation's; "learning" means estimating that equation's answer from lived samples instead of computing it from a model you were never given.
That is the whole distinction this topic exists to draw: planning is solving the Bellman equation when you know the world (value iteration, and topic 08's Dijkstra/Bellman–Ford before it); learning is solving it when you don't (Q-learning, below). Same equation, different amount of information handed to you before you start.
An MDP is a tuple (S, A, P, R, γ): states S, actions A, transition probabilities P(s'|s,a), a reward R(s,a,s'), and a discount factor γ ∈ (0,1] weighting future reward against immediate reward. The Bellman optimality equation topic 08 forward-referenced, written in full:
V*(s) = max over actions a of Σ P(s'|s,a) · [ R(s,a,s') + γ·V*(s') ]
s'
Topic 08's equation is this one's special case: deterministic transitions collapse the sum to a single term, and minimising cost is maximising negative cost, so "min" and "max" are the same instruction in different units. Value iteration (Bellman, Dynamic Programming, Princeton University Press, 1957) applies this equation as an update rule from an arbitrary starting guess and repeats it; for γ < 1 it is a contraction mapping in the max-norm, so the Banach fixed-point theorem guarantees convergence to the unique V* regardless of where it starts. This particular network needs no discounting or iteration at all to solve exactly. Every edge moves strictly S < A < B < C < D, so it is a finite, acyclic decision chain, and one backward pass from D gives the exact answer in the figure above. Value iteration was run anyway, from a starting guess of −999 at every state, and converged to that identical fixed point: the same V* and the same policy, from nowhere close to it.
Notice what did not change: the optimal policy is still S→A→B→C→D, topic 08's exact route, because it stays cheap enough that a 20% chance of a costlier detour still beats the alternative in expectation. What changed is the value, 9.384 in expectation, not a guaranteed 8, which is the entire content of adding uncertainty: the best available action can stay the same while what you should honestly expect from it gets worse.
Q-learning (Watkins & Dayan, "Q-learning," Machine Learning 8, 279–292 (1992)) solves the same equation without ever being given P or R: Q(s,a) ← Q(s,a) + α[r + γ·maxa' Q(s', a') − Q(s, a)], updated after every real (or simulated) step, using only the reward and next state actually observed. Watkins & Dayan proved convergence to Q* with probability 1 given every state–action pair visited infinitely often and a step size α satisfying the standard Robbins–Monro conditions. Run here for 200,000 sampled episodes against the identical stochastic network, never once given the 0.8/0.2 slip probabilities or the edge weights as numbers to plan with (only reward-and-next-state pairs from actually stepping through it) Q-learning recovered the exact optimal action at every one of the four decision states, with its value estimates within 0.044 of the true V* computed above (against a typical magnitude near 9.4, under 0.5% off). Verification: a script recomputes this. (For the field this one algorithm opens onto (policy gradients, actor-critic methods, and everything past tabular Q-learning) Sutton & Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, is the standard text.)
And on the quantum side of this page A superconducting qubit drifts (its resonance frequency, its gate timings, the parameters a calibration pass tuned yesterday) and for years the standard fix has been to stop the machine and recalibrate from scratch. Baum, Amico, Howell, Hush, Liuzzi, Mundada, Merkh, Carvalho & Biercuk (Q-CTRL), "Experimental Deep Reinforcement Learning for Error-Robust Gate-Set Design on a Superconducting Quantum Computer," PRX Quantum 2, 040324 (2021), arXiv 2105.01079, trained an RL agent directly against a real superconducting chip (no Hamiltonian model of the device supplied) to design an RX(π/2) single-qubit gate and a ZX(−π/2) two-qubit gate robust to the chip's own error processes. It is exactly this page's state/action/reward loop, with the environment being real hardware instead of a simulated road network.
And the machine already named on this site's QEC page Sivak, Morvan et al. (Google Quantum AI & Google DeepMind), "Reinforcement Learning Control of Quantum Error Correction," arXiv 2511.08493 (Nature, 2026), ran an RL agent on the same Willow processor already cited on this site's QEC page, but instead of stopping the machine to recalibrate, it repurposed the surface code's own error-detection events (already being produced every cycle, for decoding) as the reward signal, and let the agent steer control parameters during computation. Measured result: 3.5× more stable logical error rate under injected drift, and a new record logical error per cycle of 7.72(9)×10−&sup4; for the surface code and 8.19(14)×10−³ for the color code. Simulations scaling to tens of thousands of control parameters showed the same optimisation speed regardless of system size: evidence this is a control loop, not a one-chip trick.
Neither paper claims the RL agent discovered a new algorithm or a smarter circuit. Both are steering knobs on hardware whose job was already fixed, which is exactly the anti-hype line this site's own AI↔Q page draws everywhere else: AI reading and correcting a quantum machine's noise is real and shipping now; AI redesigning what the machine computes is a different, much less settled claim.
Check yourself
Every edge in the shortest-path example now slips onto its sibling 20% of the time. What happens to the optimal route?
The best action can stay the same while what you should honestly expect from it gets worse: "optimal" now means best on average, not best guaranteed.