SARSA (State-Action-Reward-State-Action)
Intermediate
SARSA is on-policy TD control: learn Q(s,a) using the tuple (s, a, r, s', a'). Like Qlearning but follows the behavior policy for the next action.
The problem, from first principles
Update Q values online using observed transitions. Choose the next action under the current ε-soft policy, not the greedy policy. This makes it on-policy: learns about the policy being followed.
From theory to code
Implement sarsa(env_step, num_episodes, epsilon, gamma, alpha, seed=None) which:
- Generates episodes under ε-greedy policy
- Updates Q(s,a) using: Q(s,a) = Q(s,a) + α[r + γQ(s',a') - Q(s,a)]
- Returns (Q, policy)
Constraints
- epsilon in (0, 1)
- alpha in (0, 1], learning rate
- gamma in (0, 1], discount
- Update Q immediately after each transition
- Derive policy from Q
Hints
Hint 1: Select actions epsilon-greedy
With prob 1-ε, pick argmax Q(s), else random action.Hint 2: Observe transition
From (s,a), observe (r, s'), then select a' epsilon-greedy.Hint 3: Update Q
Q(s,a) = Q(s,a) + α[r + γQ(s',a') - Q(s,a)]Keywords
rltemporal-differencecontrolon-policy
Python
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.