Tabular on-policy Sarsa control

Inputs: A finite MDP with nonempty finite state set $S$, finite nonempty action sets, discount $0\le \gamma <1$, terminal set $S_{†}\subseteq S$, an initial-state rule specifying a distribution on $S$ at each episode boundary (independent draws from a fixed $\nu$ are a special case), an episode budget $m\in \mathbb{N}\cup \{\mathrm{\infty }\}$, an initial table $Q_0:D\to \mathbb{R}$, a step-size rule giving ${\alpha }_n(S_n,A_n)\in [0,1]$ from available history before the next reward and state are observed (deterministic per-pair visit-index schedules are a special case), and an action-selection rule $\mathrm{\Pi }$ that uses the current table and available history to supply a distribution on the legal actions of the current state. Assume the Axiom of Choice for the policy path laws, that the sampling rules are measurable functions of the information available when used, and that the episodes generated by the actual rule, including within-episode changes, reach $S_{†}$ almost surely from their start states.

Interpret successive draws on finite discrete transition-record spaces, including a restart record at each episode boundary. Conditional on the full available history and its current state $s$, choose the action using the distribution supplied by $\mathrm{\Pi }$ at the current history and the next reward/state using $p(s^{\mathrm{\prime }},\rho \mid s,a)$; the initial-state rule gives the restart kernel. Require all sampling and step-size rules to be measurable with respect to their available histories. The table and counts are computed from these records. Under the stated AC assumption, the history-dependent kernel construction supplies this law, with a fixed stop symbol after a finite budget.

Output: The action-value table after every transition update and after every completed episode. A finite budget returns the final table after those episodes; budget $\mathrm{\infty }$ specifies the successive tables indefinitely and has no final output or convergence assertion.

Initialize $Q=Q_0$ and visit counts $C(s,a)=0$ for all $(s,a)\in D$. For each episode allowed by the budget, sample its start state using the initial-state rule. If it is terminal, end the episode without an update. Otherwise sample the initial action using $\mathrm{\Pi }$ with the current table and history. At each current nonterminal pair $(S_n,A_n)$, obtain ${\alpha }_n(S_n,A_n)$ from the step-size rule before observing $(R_{n+1},S_{n+1})$ from the MDP's conditional joint reward-transition law. For a visit-index schedule use $k=C(S_n,A_n)$. If $S_{n+1}\mathrm{\notin }{S}_{†}$, apply $\mathrm{\Pi }$ to the still pre-update table $Q_n$ and the available history through the new state, sample $A_{n+1}$ from that action distribution, and set

$${\delta }_n^{\mathrm{S}\mathrm{a}\mathrm{r}\mathrm{s}\mathrm{a}}=R_{n+1}+\gamma Q_n(S_{n+1},A_{n+1})-Q_n(S_n,A_n)\mathrm{.}$$

If $S_{n+1}\in S_{†}$, instead set ${\delta }_n^{\mathrm{S}\mathrm{a}\mathrm{r}\mathrm{s}\mathrm{a}}=R_{n+1}-Q_n(S_n,A_n)$ and take no terminal action. Update only the current pair:

$$Q_{n+1}(S_n,A_n)=Q_n(S_n,A_n)+{\alpha }_n(S_n,A_n){\delta }_n^{\mathrm{S}\mathrm{a}\mathrm{r}\mathrm{s}\mathrm{a}},$$

leaving every other coordinate unchanged. Increment $C(S_n,A_n)$ and output the updated table. If the next state is terminal, end the episode; otherwise set $(S,A)=(S_{n+1},A_{n+1})$ and continue. Retain the sampled $A_{n+1}$ as the action actually executed next; do not resample it after updating the table. At the following transition, the next application of $\mathrm{\Pi }$ may use the updated table and history. A policy frozen for an episode is permitted as a special case. Stop after $m$ completed episodes when $m$ is finite. The sampled next action, rather than a maximum over actions, is part of the target and is also used by the behavior process, so Sarsa is on-policy. The procedure makes no convergence claim.

Under AC, successive history-dependent probability kernels give the sampling law.

The finite state-dependent action sets and joint reward-transition law.

The discounted return and policy value.

The Sarsa TD-error and terminal-continuation conventions.

Sutton and Barto, Reinforcement Learning: An Introduction.

Yang, Optimal Control and Reinforcement Learning, Chapter 2.