Tabular Dyna-Q with a deterministic last-observation model

Input: a finite continuing discounted MDP with $0\le \gamma <1$, deterministic one-step rewards in $[0,1]$ and deterministic next states at every state–action pair, an initial state $s_0$, a behavior rule that selects an admissible action at each visited state, an integer $n\ge 0$ of planning updates per real interaction, a step-size schedule assigning $\alpha \in (0,1]$ to each Q-table update, and a finite initial action-value table $Q_0:D\to \mathbb{R}$, where $D=\{(s,a):s\in S,a\in A(s)\}$. An episodic task may be represented by an ordinary transition to its reset state. Initialize an empty model table and, for each state $s$, an empty set $A_{\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{n}}(s)$.

For each real interaction, let $s$ be the current state, choose $a$ using the behavior rule, execute it in the environment, and observe reward $r$ and next state $s^{\mathrm{\prime }}$. Apply one tabular Q-learning update to $Q(s,a)$:

$Q(s,a)\leftarrow Q(s,a)+\alpha [r+\gamma {\max }_{b\in A(s^{\mathrm{\prime }})}Q(s^{\mathrm{\prime }},b)-Q(s,a)]\mathrm{.}$

Record the deterministic response $\mathrm{Model}(s,a)=(r,s^{\mathrm{\prime }})$ and insert $a$ into $A_{\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{n}}(s)$. Then perform $n$ planning updates: choose uniformly a state from $S_{\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{n}}=\{s:A_{\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{n}}(s)\mathrm{\ne }\mathrm{\varnothing }\}$, choose uniformly an action from its $A_{\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{n}}(s)$, retrieve the saved response $(\tilde{r},{\tilde{s}}^{\mathrm{\prime }})=\mathrm{Model}(s,a)$, and apply the same Q-learning update with $(\tilde{r},{\tilde{s}}^{\mathrm{\prime }})$ and the next scheduled step size. The model is queried only at previously experienced pairs. In the stated deterministic environment the stored response is exact after that pair is first observed. After the planning updates, set the current state to $s^{\mathrm{\prime }}$ and output the updated Q table together with the real action for this interaction. Repeat for successive real interactions indefinitely, unless the caller stops the run. The procedure makes no claim that the model is accurate at unseen pairs or in a stochastic environment, and it asserts no convergence guarantee.

A finite MDP supplies the finite state/action sets, reward law, and transition law.

A finite model assigns a reward prediction and transition distribution on each admissible pair; a deterministic stored response is a point-mass sample model.

One tabular Q-learning update changes only the visited coordinate using the reward-plus-greedy-continuation target.

Sutton and Barto, Reinforcement Learning: An Introduction.