Discounted returns and policy values in a finite MDP

Let a finite MDP have $0\le \gamma <1$ and let $\pi$ be a stationary Markov policy. If $S=\mathrm{\varnothing }$, define $V^{\pi }$ to be the unique empty function; no path law or choice axiom is needed in this case. If $S\mathrm{\ne }\mathrm{\varnothing }$, assume the Axiom of Choice and, for each $s\in S$, use the path law started at $X_0=(s,0)$ supplied by the policy-induced reward-state chain; write $X_t=(S_t,R_t)$. The discounted return is

$G_t={\sum }_{j=0}^{\mathrm{\infty }}{\gamma }^j{R}_{t+j+1},$

and the state value under $\pi$ is $V^{\pi }(s)={\mathbb{E}}_{\pi ,s}[G_0]$, where ${\mathbb{E}}_{\pi ,s}$ is expectation under that start-state law. If $S=\mathrm{\varnothing }$, $V^{\pi }$ is the unique empty function. The reward sequence bound gives $\mathrm{\mid }{G}_t\mathrm{\mid }\le M\mathrm{/}(1-\gamma )$, so each return is measurable and integrable. This is the start-state meaning of ${\mathbb{E}}_{\pi }[G_t\mid S_t=s]$ when that conditional expectation is defined. The definition concerns discounted infinite-horizon tasks; average-reward and undiscounted continuing models, and improper episodic tasks, are outside its scope.

The coordinate $0$ in $X_0=(s,0)$ is only a dummy initial reward; the chain's one-step kernel emits rewards in $\mathcal{R}$. Finite partial sums of the return are measurable, their pointwise limit is measurable, and the constant bound $M\mathrm{/}(1-\gamma )$ is an integrable majorant on the probability space.

The finite joint reward-transition model and its bounded reward alphabet.

The Axiom of Choice, used only in the nonempty-state path-law branch.

The policy-induced homogeneous reward-state chain and its start-state path law.

The conditional one-step transition-kernel identity defining a homogeneous Markov chain.

Absolute convergence and the uniform tail bound for bounded discounted rewards.

Finite sums and scalar multiples of measurable functions are measurable.

A measurable real-valued coordinate on a probability space is a real random variable.

A pointwise limit of measurable functions is measurable.

A measurable pointwise limit under one integrable majorant is integrable, and its expectations are the limits of the partial expectations.

Expectation of an integrable real random variable is its finite Lebesgue integral.

Sutton and Barto, Reinforcement Learning: An Introduction.

Kaelbling, Littman, and Cassandra, Brown Technical Report CS-96-08.