Tabular Q-learning

Inputs: A finite MDP with nonempty finite state set $S$, finite nonempty action sets $A(s)$, finite reward alphabet $\mathcal{R}$, and discount $0\le \gamma <1$; an initial state $S_0\in S$; a behavior rule that selects a legal action using the interaction history available at time $n$; an initial table $Q_0\in {\mathbb{R}}^D$; and a step-size rule that, before observing the next reward and state, supplies ${\alpha }_n(S_n,A_n)\in [0,1]$ from the history and selected pair. A deterministic per-pair schedule ${\alpha }_k(s,a)\in [0,1]$ based on the number of previous visits to $(s,a)$ is a special case. The interaction must, conditional on its history and the selected pair $(S_n,A_n)$, draw $(S_{n+1},R_{n+1})$ with joint mass $p(s^{\mathrm{\prime }},\rho \mid S_n,A_n)$.

Output: The action-value table after every interaction, $(Q_n{)}_{n\ge 0}$; a finite run outputs its current table $Q_n$.

Initialize $Q=Q_0$. For each $n=0,1,2,\dots$, select $A_n$ by the behavior rule, obtain ${\alpha }_n(S_n,A_n)$ from the step-size rule, and observe $(R_{n+1},S_{n+1})$. Compute

$${\delta }_n=R_{n+1}+\gamma \underset{b\in A(S_{n+1})}{\max }{Q}_n(S_{n+1},b)-Q_n(S_n,A_n),$$

then update only the visited coordinate by

$$Q_{n+1}(S_n,A_n)=Q_n(S_n,A_n)+{\alpha }_n(S_n,A_n){\delta }_n\mathrm{.}$$

Leave every other coordinate unchanged, set the current table to $Q_{n+1}$, and set the current state to $S_{n+1}$. The target uses the greedy maximum even when the behavior rule explores, so this is off-policy and uses no importance-sampling ratio. The procedure makes no convergence claim; convergence requires additional hypotheses not imposed here.

The finite state set, admissible state-action pairs, and joint reward-transition law.

The expected reward-plus-greedy-continuation action-value map targeted by Q-learning.

Sutton and Barto, Reinforcement Learning: An Introduction.

Yang, Optimal Control and Reinforcement Learning, Chapter 2.