An $\ell_1$ ball of probability vectors is nonempty and compact

Let $c$ be a probability vector on a finite set $\iota$ and let $\beta\ge0$. Then the set

of probability vectors within $L^1$ distance $\beta$ of $c$ is nonempty and compact.

This is the confidence set used by UCRL2: $c$ is the empirical transition row $\hat P_a(s)$ and $\beta$ the confidence radius supplied by Weissman's inequality. Nonemptiness and compactness are exactly the hypotheses under which the extended MDP — whose actions are the pairs (action, transition row in the confidence set) — has a solution of its Bellman optimality equation, so this lemma is what connects the statistical part of the analysis to the planning part.

Nonemptiness holds because $c$ itself lies in $\mathcal C$. For compactness, note first that $\mathcal C$ is contained in the cube $[0,1]^{\iota}$: each coordinate is nonnegative and, being one term of a sum of nonnegative numbers equal to $1$, is at most $1$. The cube is compact by Tychonoff's theorem. Finally $\mathcal C$ is closed, being the intersection of the closed sets $\{p : p_i \ge 0\}$, the level set $\{p : \sum_i p_i = 1\}$ and the sublevel set $\{p : \sum_i |p_i - c_i| \le \beta\}$, all closed because the coordinate projections, and hence the finite sums and absolute values built from them, are continuous. A closed subset of a compact set is compact.