Termination of extended value iteration under communicating assumptions

For a probability vector $p$ and $0\le \alpha \le 1$, the ball $Q=\{q\in \mathrm{\Delta }(S):\mathrm{\parallel }q-p{\mathrm{\parallel }}_1\le 2\alpha \}$ equals the set of $z+w$ with $0\le z\le p$, $\sum z=1-\alpha$, $w\ge 0$, and $\sum w=\alpha$. If $q\in Q$, the coordinatewise minimum $p\wedge q$ has mass $1-\mathrm{\parallel }p-q{\mathrm{\parallel }}_1\mathrm{/}2\ge 1-\alpha$; scaling it down to mass $1-\alpha$ gives $z\le q$, and $w=q-z$. This also covers $\alpha =0$; for $\alpha =1$, take $z=0$. Conversely, $p-z$ and $w$ are nonnegative vectors of mass $\alpha$, so $\mathrm{\parallel }z+w-p{\mathrm{\parallel }}_1\le 2\alpha$. Thus the support function is $\alpha {\max }_{j}v(j)+H_p^{\alpha }(v)$, where $H_p^{\alpha }(v)={\max }_{0\le z\le p,\sum z=1-\alpha }z\cdot v$. The maximizing sets are nonempty and compact, since the simplex and the coordinatewise constrained sets are closed and bounded. The formula includes radii at least $2$, for which $\alpha =1$ and the ball is the whole simplex.

Fix a center $p$, a value vector $v$, and $\alpha =\min \{1,b\mathrm{/}2\}$. Each routine update preserves the coordinate sum, keeps coordinates in $[0,1]$, and transfers at most the remaining budget $c$. Since every transfer has $j<\mathrm{\ell }$ and the pointers move only inward, its source and destination supports remain disjoint; the final vector is a probability vector at distance $2R\le 2\alpha \le b$ from $p$, where $R$ is the total transferred mass. Any feasible $q^{\mathrm{\prime }}$ moves a mass $R=\mathrm{\parallel }{q}^{\mathrm{\prime }}-p{\mathrm{\parallel }}_1\mathrm{/}2\le \alpha$ from coordinates it decreases to coordinates it increases; the decrease capacities are $p_i$ and the increase capacities are $1-p_i$. Its gain $v\cdot (q^{\mathrm{\prime }}-p)$ is at most the gain obtained by removing mass $R$ from the lowest-valued available coordinates and adding mass $R$ to the highest-valued available coordinates. This follows by exchanging any removed mass at a higher-valued source with available mass at a lower-valued source, and any added mass at a lower-valued destination with available capacity at a higher-valued destination. As $R$ increases, the marginal source values are nondecreasing and the marginal destination values are nonincreasing, so the maximum gain increases while the largest remaining destination-minus-source value is positive and cannot increase after that value becomes nonpositive. The routine implements exactly these allocations and stops only when the budget is spent or every remaining marginal gain is nonpositive. Hence it attains the maximum gain over all $R\le \alpha$. Each positive transfer exhausts one of at most $\mathrm{\mid }S\mathrm{\mid }$ source capacities or $\mathrm{\mid }S\mathrm{\mid }$ destination capacities, or spends the remaining budget, so there are at most $2\mathrm{\mid }S\mathrm{\mid }+1$ positive transfers.

Put ${\alpha }_{s,a}=\min \{1,b_p(s,a)\mathrm{/}2\}$. If $\eta <1$, steps 1.1 and 2.1 give $F(v)=\eta {\max }_{j}v(j)\mathbf{1}+(1-\eta )G(v)$, where $G(v)(s)={\max }_a\frac{\tilde{r}(s,a)+({\alpha }_{s,a}-\eta ){\max }_{j}v(j)+H_{{\widehat{P}}_{s,a}}^{{\alpha }_{s,a}}(v)}{1-\eta }\mathrm{.}$ The map $G$ is monotone in every coordinate. Each expression inside its maximum increases by $c$ on replacing $v$ by $v+c\mathbf{1}$, because its coefficient mass is $({\alpha }_{s,a}-\eta )+(1-{\alpha }_{s,a})=1-\eta$. Thus $G(v+c\mathbf{1})=G(v)+c\mathbf{1}$. If $m=\min (v-w)$ and $M=\max (v-w)$, monotonicity applied to $w+m\mathbf{1}\le v\le w+M\mathbf{1}$ implies $m\mathbf{1}\le G(v)-G(w)\le M\mathbf{1}$. The common scalar term in the expression for $F$ disappears from span, giving $\mathrm{span}(F(v)-F(w))\le (1-\eta )\mathrm{span}(v-w)$.

Apply step 3.1 repeatedly to $u_i=F(u_{i-1})$ and $u_{i-1}=F(u_{i-2})$. This proves the displayed geometric bound by induction. Its right side tends to zero, so the strict span test holds at some finite iteration for every positive tolerance. If $\eta =1$, every row ball is the whole simplex and $F(v)(s)={\max }_a\tilde{r}(s,a)+{\max }_{j}v(j)$; hence $F(v)-F(w)$ is constant across states and every increment after the first has zero span. UCRL2's logarithms, denominators, and tolerance at every finite $t_k\ge 1$, $\delta \in (0,1)$ give positive radii and tolerance, so this applies to each episode without any confidence-event qualification.

With fixed finite tie orders, sorting, coordinate updates, maxima, and comparisons in each row routine are Borel functions of the real estimates; step 2.1 bounds the number of transfers uniformly. Thus each finite Bellman update and its selected action and rows are Borel. For each integer $i$, the event that the stopping test first succeeds at iteration $i$ is Borel, and the returned quantities restricted to that event are Borel. Step 4.1 shows that, under positive radii and positive tolerance, these events cover all inputs. Therefore the returned policy, rows, value vector, and stopping index are measurable functions of the estimates.