An engineer describes an RL agent that learns action-value estimates from experience gathered under an exploratory behavior policy, while the estimates themselves converge toward the optimal greedy policy. Which classic algorithm best matches this description?
Select an answer to reveal the explanation.
Short Explanation
You've just described Q-learning, and here's why. Q-learning is off-policy and value-based, meaning it estimates Q-values, the expected return of taking an action in a state, but it updates those estimates using the best possible next action, not necessarily the action the agent actually took. So the agent can explore with an epsilon-greedy policy while its Q-table quietly learns the optimal greedy policy underneath. REINFORCE is out because it's a policy-gradient method that directly optimizes a policy, no Q-values involved. SARSA is close in spirit but it's on-policy, it updates using the action actually taken next, not the max. Behavior cloning isn't RL at all, it's just supervised learning from demonstrations, no reward signal or trial-and-error.
Full Explanation
Q-learning is a foundational off-policy, value-based reinforcement learning algorithm. It maintains a table (or function approximator) of action-value estimates, Q(s,a), representing the expected cumulative reward of taking action a in state s and then following the optimal policy afterward. The defining trait of Q-learning is its update rule: it bootstraps using the maximum Q-value over all possible next actions, regardless of which action the behavior policy actually selects next. This decoupling of the policy used to generate experience (often epsilon-greedy, to ensure exploration) from the policy being learned (the greedy policy implied by the current Q-values) is exactly what makes Q-learning off-policy. Over time, as the agent explores the environment, its Q-value estimates converge toward the true optimal action-values, from which the optimal policy can be extracted by always selecting the highest-valued action.
SARSA is incorrect because, while structurally similar to Q-learning and also a temporal-difference method, it is on-policy: its update uses the Q-value of the action actually selected next by the current behavior policy, not the maximum possible Q-value. This makes SARSA's learned values reflect the policy being followed, including its exploratory mistakes, whereas Q-learning's values reflect the optimal policy regardless of how exploration is conducted. REINFORCE is incorrect because it belongs to a different family entirely, policy-gradient methods, which parameterize the policy directly and adjust its parameters via gradient ascent on expected return, using Monte Carlo returns rather than learned action-value estimates. Behavior cloning is incorrect because it is not reinforcement learning in the classical sense; it is a supervised learning technique that trains a policy to mimic expert-provided state-action pairs, with no reward function, exploration, or environment interaction driving the learning process.
A helpful memory aid: 'Q-learning learns about the best policy while behaving differently' captures the off-policy distinction, whereas SARSA's mnemonic (State-Action-Reward-State-Action) reflects that it only ever learns about the policy it is actually executing.