Expected SARSA Target
Problem Statement
Expected SARSA replaces the sampled next action with the expectation under the next-state policy:
target=r+γ∑a​π(a∣s′)Q(s′,a)
Given reward r, discount gamma, next-state policy pi_next and action values q_next (aligned), implement expected_sarsa_target(reward, gamma, pi_next, q_next) returning a float.
Example:
expected_sarsa_target(1.0, 0.9, [0.5, 0.5], [2.0, 4.0])
3.7
- Calculate the expected action value for the next state by taking the dot product of the policy probabilities and the corresponding Q-values: 0.5×2.0+0.5×4.0=1.0+2.0=3.0.
- Multiply this expected value by the discount factor γ to account for the temporal distance of future rewards: 0.9×3.0=2.7.
- Add the immediate reward to the discounted expected future value to form the target: 1.0+2.7=3.7.
- The final output is 3.7
Constraints:
len(pi_next) == len(q_next),pi_nextsums to 1.- Return a float.
1. Background Knowledge
In reinforcement learning, Temporal-Difference (TD) learning updates value estimates using observed rewards and the estimated value of the next state, rather than waiting for a full episode to finish. SARSA is an on-policy TD control algorithm that updates Q(s,a) based on the actual next state s′, next action a′, and reward r it experiences. The SARSA target is r+γQ(s′,a′), where a′ is the action actually chosen by the current policy.
Expected SARSA is a variant that avoids the high variance introduced by sampling a single next action. Instead of using the specific Q(s′,a′) for the sampled action, it computes the expectation of Q(s′,a) over all possible actions a, weighted by the policy π(a∣s′). The target becomes:
target=r+γa∑​π(a∣s′)Q(s′,a)This is essentially a weighted average of the action values in the next state, where the weights are the probabilities assigned by the policy. Because it uses the full policy distribution, Expected SARSA has lower variance than standard SARSA but may converge more slowly in some settings. It remains on-policy because the expectation is taken under the same policy used for action selection.
2. Algorithm Approach
The core operation is a dot product between two vectors of equal length: the policy probabilities π(a∣s′) and the action values Q(s′,a). The algorithm pattern is:
- Compute the weighted sum ∑a​π(a∣s′)Q(s′,a), which is the expected action value in the next state.
- Multiply this expectation by the discount factor γ.
- Add the immediate reward r to obtain the TD target.
This is a straightforward vectorized reduction operation. No iterative loops over states or episodes are needed—just a single inner product over the action space.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.