Trial-based real-time dynamic programming

Input: a finite stochastic shortest-path model, a finite value table $V_0:S\to \mathbb{R}$ with $V_0(g)=0$ on goals, a nonempty finite start set $S_0\subseteq S\setminus G$, a positive integer trial cap $L$, and an infinite supplied start sequence in which each member of $S_0$ occurs infinitely often. For each trial, set the current state to the next supplied start. For at most $L$ decision steps, or until a goal is reached, do the following: at the current nonglobal state $s$, compute

$q_V(s,a)=r(s,a)+{\sum }_{s^{\mathrm{\prime }}\in S}P(s^{\mathrm{\prime }}\mid s,a)V(s^{\mathrm{\prime }})(a\in A(s)),$

choose uniformly from the nonempty set of actions attaining ${\max }_{a\in A(s)}{q}_V(s,a)$ using a fresh tie draw, execute the chosen action in the given MDP and observe the next state, then replace $V(s)$ by ${\max }_{a\in A(s)}{q}_V(s,a)$ using the value table from before that backup. Keep every other value unchanged. At a goal keep value $0$. After a trial ends, reset the state to the next supplied start without resetting the value table. The procedure returns the successive value tables and selected actions; it asserts no convergence guarantee by itself.

The finite undiscounted MDP has absorbing zero-reward goals and strictly positive expected costs away from them.

Every finite nonempty set of real action values has an attained maximum.

Barto, Bradtke, and Singh, “Learning to Act Using Real-Time Dynamic Programming”.