Discounted Bellman solution over compact confidence sets

Fix $S$ states and $A$ actions, a reward function $r_a(s)\in[0,1]$, and for each state-action pair a nonempty compact set $\mathcal C_{s,a}$ of probability vectors on the state space. For every discount factor $\gamma\in[0,1)$ there are a value function $V:\mathcal S\to[0,\tfrac{1}{1-\gamma}]$, an action map $f$ and transition rows $q(s)\in\mathcal C_{s,f(s)}$ such that

Together these say that $V$ solves the discounted Bellman optimality equation $V(s)=\max_a\max_{p\in\mathcal C_{s,a}}\big(r_a(s)+\gamma\langle p,V\rangle\big)$ of the extended MDP, whose actions are the pairs $(a,p)$ with $p\in\mathcal C_{s,a}$, and that the maximum is attained at $(f(s),q(s))$.

This is the fixed point computed by the extended value iteration of UCRL2: the confidence sets are the $L^1$ balls around the empirical transition rows, and the extended MDP is the one whose transition matrices range over the confidence region. It is not a finite MDP — its action set is a continuum — so the usual finite-action argument does not apply verbatim.

What replaces finiteness is compactness. The inner maximisation $\mathrm{opt}(\mathcal C_{s,a}, v)=\max\{\langle p,v\rangle : p\in\mathcal C_{s,a}\}$ is attained because a continuous image of a compact set is a compact set of reals and therefore contains its supremum. Moreover $v\mapsto \mathrm{opt}(\mathcal C_{s,a},v)$ is $1$-Lipschitz for the supremum norm, because every $p\in\mathcal C_{s,a}$ is a probability vector and hence $\langle p,u\rangle\le\langle p,v\rangle+\|u-v\|_\infty$. Consequently the operator $(Tv)(s)=\max_a\big(r_a(s)+\gamma\,\mathrm{opt}(\mathcal C_{s,a},v)\big)$ is a $\gamma$-contraction of $\mathbb R^{\mathcal S}$, and Banach's fixed point theorem supplies $V$; the maximisers over the finite action set and over the compact confidence set supply $f$ and $q$. Evaluating the fixed point equation at a state where $V$ is largest gives $V\le\frac{1}{1-\gamma}$, and at a state where it is smallest gives $V\ge0$.