How do the Q-learning and SARSA update rules differ, and which one is off-policy?

## The setting Both methods solve the same problem: **control** in a Markov decision process whose transition and reward model you do not have. The agent is in a state `s`, picks an action `a`, receives a reward `r`, and lands in `s'`. Learning happens in a **table** with one entry per state-action pair — this is the *tabular* case, where states and actions are finite and each `Q(s,a)` is stored and updated independently. The quantity being learned, `Q(s,a)`, is the **action value**: the expected discounted return from taking action `a` in state `s` and following a particular policy afterwards. `gamma` in `[0,1)` is the discount factor, which decides how much future reward counts. Once the table is good, acting is trivial: in state `s`, take `argmax_a Q(s,a)`. ## The two updates Both have the same shape — move the stored value a fraction `alpha` of the way toward a one-step target: ``` Q(s,a) <- Q(s,a) + alpha * ( target - Q(s,a) ) ``` Q-learning: ``` target = r + gamma * max over a' of Q(s', a') ``` SARSA: ``` target = r + gamma * Q(s', a') where a' is the action the agent actually takes next ``` At a terminal transition both targets collapse to just `r` — there is no next state to bootstrap from, and forgetting that is a classic implementation bug that quietly poisons the values near the goal. Equivalently, `Q <- (1 - alpha) * Q + alpha * target`: the new estimate is a blend of what you believed and what this one sample suggests. ## Why one is off-policy and the other on-policy Two policies are in play in any learning agent. The **behaviour policy** chooses the actions that generate the data — typically epsilon-greedy, taking the current best action most of the time and a random action with probability epsilon. The **target policy** is the one whose value you are estimating. - Q-learning's `max` operator hard-codes the target policy as *greedy*, regardless of what the behaviour policy did next. Behaviour and target differ, so it is **off-policy**. The payoff is real: you can behave cautiously — a deliberately conservative lane-change controller that only ever makes gentle merges — while the table underneath converges toward the value of the aggressive greedy policy you never actually ran. The behaviour policy only has to keep visiting every state-action pair; it does not have to be good. - SARSA's target contains the action its own policy actually selected, exploration and all. Behaviour and target are the same object, so it is **on-policy**. It answers "what is this epsilon-greedy agent worth?", and improving greedily with respect to those values improves that same agent. A useful consequence: if the behaviour policy is fully greedy, then `a' = argmax_a' Q(s',a')` on every step and the two updates are numerically identical. The algorithms only separate when the agent explores. ## What each converges to Under the usual tabular conditions — bounded rewards, every state-action pair visited infinitely often, and a step size that decays appropriately — Q-learning converges to `Q*`, the optimal action values, *without any requirement that the behaviour policy improve at all*. SARSA converges to the optimal values too, but only if its policy becomes greedy in the limit while still exploring infinitely often; with a fixed exploration rate it converges instead to the values of that fixed epsilon-greedy policy, which is a genuinely different fixed point. ## A near relative Expected SARSA replaces the sampled `Q(s',a')` with the expectation under the policy, `sum over a' of pi(a'|s') * Q(s',a')`. It removes the variance contributed by randomly drawing `a'` at the cost of a little more arithmetic per step, and if `pi` is greedy it reduces exactly to Q-learning — which shows the whole family is one design choice about which next-state value to bootstrap from. ## Confusions worth clearing "Off-policy means it does not explore" is wrong: Q-learning explores just as much, it simply refuses to let the exploratory action into its target. "SARSA is the safe one and Q-learning the good one" is a slogan, not a mechanism — the mechanism is which next-state value enters the bracket. And neither method needs a model of the environment; both learn purely from sampled transitions.