First-visit Monte Carlo policy evaluation

Inputs: A finite MDP with nonempty finite state set $S$, discount $0\le \gamma <1$, terminal set $S_{†}\subseteq S$, an initial-state rule, and an episode budget $N\in \mathbb{N}\cup \{\mathrm{\infty }\}$. Assume the Axiom of Choice for the policy path laws defining $V^{\pi }$ and the episode distributions, and that episodes reach $S_{†}$ in finite time almost surely from every state under each stationary policy used: the target $\pi$, and also the behavior $\mu$ in off-policy mode. Choose one mode: (a) on-policy prediction with independent episodes under a stationary target policy $\pi$; or (b) off-policy prediction with independent episodes under a stationary behavior policy $\mu$ and stationary target policy $\pi$. In off-policy mode require $\pi (a\mid x)>0\Rightarrow \mu (a\mid x)>0$ for every nonterminal state $x$ and action $a\in A(x)$.

Output: After every finite number $n$ of completed episodes, for every nonterminal state its visit count and each available estimate; report no estimate when its required denominator is zero. A finite budget $N$ returns these outputs after episode $N$; budget $\mathrm{\infty }$ emits successive finite-prefix outputs without a final output or convergence assertion. Set the value estimate of every terminal state to $0$.

Initialize visit counts $C(s)=0$ and leave each nonterminal state's estimate unavailable. Generate successive independent episodes using the selected mode and initial-state rule; stop after $N$ episodes when $N$ is finite. In episode $i$, for each nonterminal state $s$ visited before termination, let $t_i(s)$ be its first visit time and let $G_{t_i(s)}={\sum }_{k=t_i(s)}^{T_i-1}{\gamma }^{k-t_i(s)}{R}_{k+1}$ be the return from that visit.

In on-policy mode, update only on this first visit: set $m=C(s)+1$; if $m=1$, set $\widehat{V}(s)=G_{t_i(s)}$, and otherwise set

$$\widehat{V}(s)\leftarrow \widehat{V}(s)+\frac{G_{t_i(s)}-\widehat{V}(s)}{m}\mathrm{.}$$

Then set $C(s)=m$. In off-policy mode, for each first visit compute

$$W_i(s)=\prod _{k=t_i(s)}^{T_i-1}\frac{\pi (A_k\mid S_k)}{\mu (A_k\mid S_k)},$$

where $T_i$ is the terminal time and an empty product is $1$. Maintain $B(s)=0$ and $W_{\mathrm{\Sigma }}(s)=0$ initially; add $W_i(s)G_{t_i(s)}$ to $B(s)$ and $W_i(s)$ to $W_{\mathrm{\Sigma }}(s)$, and increment $C(s)$. After any $n$ completed episodes, the ordinary first-visit estimator is

$${\widehat{V}}_n^{\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{r}\mathrm{y}}(s)=\frac{B(s)}{C(s)}$$

when $C(s)>0$; otherwise no ordinary estimate is produced. The weighted first-visit estimator is

$${\widehat{V}}_n^{\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}\mathrm{e}\mathrm{d}}(s)=\frac{B(s)}{W_{\mathrm{\Sigma }}(s)}$$

when $W_{\mathrm{\Sigma }}(s)>0$; otherwise no weighted estimate is produced. Under target support, for each positive-probability behavior history ending immediately upon a first visit to a nonterminal state $s$, before its action is sampled, the ordinary weighted return has conditional mean $V^{\pi }(s)$ by the finite-episode likelihood-ratio identity. The self-normalized weighted estimator need not be unbiased at a finite sample size. These procedures make no convergence claim or Monte Carlo control claim.

The finite MDP and stationary policies.

Discounted returns and state values.

Finite episodes, first-visit returns, support, and trajectory ratios.

The ordinary importance-sampling return has target-policy conditional mean under support.

Sutton and Barto, Reinforcement Learning: An Introduction.

Yang, Optimal Control and Reinforcement Learning, Chapter 2.