Expected regret lower bound for communicating MDPs

We use the proved local Pinsker inequality and the total-variation bound for expectations. All remaining probability calculations are supplied here. Write $\mathrm{kl}(p,q)$ for Bernoulli relative entropy. For $0<p<p+e<1$, $\mathrm{kl}(p,p+e)={\int }_p^{p+e}\frac{x-p}{x(1-x)}dx\le \frac{e^2}{2p(1-p-e)}\mathrm{.}$ Indeed, differentiating $p\log (p\mathrm{/}x)+(1-p)\log ((1-p)\mathrm{/}(1-x))$ gives the integrand, and $x(1-x)\ge p(1-p-e)$ on the integration interval. Suppose two environments differ only at a single state-action pair $j$, at which one Bernoulli observation parameter changes from $p$ to $p+e$. Let $P_0$ and $P_j$ be their complete histories through the $T$th transition/reward, and let $N_j$ count uses of pair $j$. Their likelihood ratio is the product of the changed Bernoulli likelihood ratios at those uses. The initial law and all conditional action kernels are identical and cancel, including for randomized algorithms. Taking logarithms, conditioning on each past history and selected action, and summing gives exactly $\mathrm{KL}(P_0\mathrm{\parallel }{P}_j)={\mathbb{E}}_0[N_j]\mathrm{kl}(p,p+e)\mathrm{.}$ There is no absolute-continuity issue because both Bernoulli parameters lie strictly between zero and one and every unchanged kernel has the same support. The displayed identity also follows directly by expanding the finite history probabilities; all rewards used below have finite support. Since $0\le N_j\le T$, Pinsker implies ${\mathbb{E}}_j{N}_j\le {\mathbb{E}}_0{N}_j+T\sqrt{\mathrm{KL}(P_0\mathrm{\parallel }{P}_j)\mathrm{/}2}\mathrm{.}$ For a family of $K$ candidate pairs with $n_j={\mathbb{E}}_0{N}_j$ and ${\sum }_j{n}_j\le mT$, Cauchy–Schwarz gives $K^{-1}{\sum }_j\sqrt{n_j}\le \sqrt{mT\mathrm{/}K}$. These arguments hold for every algorithm without a deterministic-policy reduction.

First suppose $D\ge 16$. In this branch, set $k=\lfloor S\mathrm{/}2\rfloor ,b=\lfloor A\mathrm{/}3\rfloor ,B=A-b-1,K=kB,p=\frac{8}{3D},e=\frac{7}{20}\sqrt{\frac{pK}{T}}\mathrm{.}$ There are $k$ paired bad/good states $(x_i,y_i)$. If $S$ is odd, include one additional bare routing state. Arrange the bad states and the optional bare state into a breadth-first rooted $b$-ary tree of height $h$. At each bad state, $B$ useful actions have reward zero and move to its good partner with probability $p$, otherwise staying put. The remaining $b+1$ actions route deterministically toward the parent or one of the $b$ child slots, with missing slots giving self-loops; their rewards are zero. At each good state all $A$ actions have reward one and move to the paired bad state with probability $p$, otherwise staying put. At the optional bare state use the same routing actions and duplicate them to obtain exactly $A$ actions, all with reward zero. This uses exactly $S$ states and exactly $A$ actions per state. For each of the $K$ useful pairs $j$, environment $M_j$ changes just that pair's probability of entering its good state from $p$ to $p+e$. The baseline $M_0$ has no change. Fix the initial state at the bad root. Every environment is communicating.

For every integer $A\ge 10$, $B\ge \frac{7}{12}A,B\le \frac{2}{3}A,b\ge A^{2\mathrm{/}5},2b^2\ge A^{6\mathrm{/}5}\mathrm{.}$ For the first inequality, $A\ge 12$ gives $B\ge 2A\mathrm{/}3-1\ge 7A\mathrm{/}12$, and $A=10,11$ are immediate. The second follows from $\lfloor A\mathrm{/}3\rfloor \ge (A-2)\mathrm{/}3$. For the last inequality, check $A=10,11,12,13$ directly; for $A\ge 14$, $b\ge A\mathrm{/}4$ and $A^{4\mathrm{/}5}\ge 8$, so $2b^2\ge A^2\mathrm{/}8\ge A^{6\mathrm{/}5}$. This last inequality implies $b\ge A^{2\mathrm{/}5}$ because $A^{1\mathrm{/}5}\ge \sqrt{2}$. The number of tree vertices is $n=\lceil S\mathrm{/}2\rceil$. If $h=2$, breadth-first filling implies $n\ge b+2$, so $S\ge 2b+3\ge 2A\mathrm{/}3\ge A^{4\mathrm{/}5}$ and hence $h\le (5\mathrm{/}2){\log }_{A}S$. If $h\ge 3$, it implies $S\ge 2b^{h-1}$, so $S\ge (2b^2)b^{h-3}\ge A^{6\mathrm{/}5}{A}^{(2\mathrm{/}5)(h-3)}=A^{2h\mathrm{/}5}\mathrm{.}$ Thus always $h\le \max \{1,(5\mathrm{/}2){\log }_{A}S\}\le D\mathrm{/}8$. The final inequality uses $D\ge 16$ and $D\ge 20{\log }_{A}S$. To hit a target good state from any state, first leave an initial good state if necessary (mean at most $1\mathrm{/}p$), follow the tree path (at most $2h$ steps), and repeatedly take a useful action at the target bad state (mean at most $1\mathrm{/}p$). Hitting bad or bare targets takes no longer. Consequently $\mathrm{diam}(M_j)\le \frac{2}{p}+2h\le \frac{3D}{4}+\frac{D}{4}=D\mathrm{.}$

In $M_j$ the optimal average reward is ${\rho }^{\ast }=\frac{p+e}{2p+e}=\frac{1}{2}+\frac{e}{4p+2e}\mathrm{.}$ To prove this, take the function $v$ equal to $1\mathrm{/}(2p+e)$ at every good state and zero elsewhere. At every state-action pair, $r+Pv-v\le {\rho }^{\ast }$: equality holds at good states and the special useful pair, ordinary useful pairs give $p\mathrm{/}(2p+e)$, and routes give zero. Summing this inequality in conditional expectation gives average reward at most ${\rho }^{\ast }$, because $v$ is bounded. Routing to the special bad state and then always using its special action realizes the two-state chain with transitions $p+e$ and $p$, whose invariant good-state mass is $(p+e)\mathrm{/}(2p+e)$. Its convergence in Cesàro mean follows directly from the two-state recurrence; the finite expected routing/hitting transient changes no average reward. This proves the formula. Let $G_t$ be the indicator that the current state is good, let $U_t$ indicate a useful action at a bad state, and let $Q_t$ indicate a routing action (including every action at the bare state). Then $G_t+U_t+Q_t=1$ and ${\mathbb{E}}_j[G_{t+1}-G_t\mid \text{history, action}]=p{U}_t+e\mathbf{1}\{j\text{ used at }t\}-p{G}_t\mathrm{.}$ Rewards equal $G_t$. Since $G_1=0$, summing the equality gives the exact identity ${\mathbb{E}}_j{R}_T=\frac{T}{2}-\frac{1}{2}{\mathbb{E}}_j{\sum }_{t=1}^T{Q}_t+\frac{e}{2p}{\mathbb{E}}_j{N}_j-\frac{{\mathbb{E}}_j{G}_{T+1}}{2p}\mathrm{.}$ In particular, ${\mathbb{E}}_j[T{\rho }^{\ast }-R_T]\ge \frac{eT}{4p+2e}-\frac{e}{2p}{\mathbb{E}}_j{N}_j\mathrm{.}$ There is no adverse additive initial-transient term. In the baseline, the same identity with $e=0$ yields ${\sum }_{j=1}^K{\mathbb{E}}_0{N}_j={\mathbb{E}}_0{\sum }_t{U}_t=\frac{T}{2}-\frac{1}{2}{\mathbb{E}}_0{\sum }_t{Q}_t+\frac{{\mathbb{E}}_0{G}_{T+1}}{2p}\le \frac{T}{2}+\frac{1}{2p}\mathrm{.}$

We have $k\ge 5S\mathrm{/}11$ (even $S$ is immediate, and odd $S\ge 11$ gives $(S-1)\mathrm{/}(2S)\ge 5\mathrm{/}11$), so $30\le K,\frac{35}{132}SA\le K\le \frac{1}{3}SA\mathrm{.}$ Because $pT\ge (8\mathrm{/}3)SA$, $\frac{e}{p}\le \frac{7}{20\sqrt{8}}<\frac{1}{8},p\le \frac{1}{6},1-p-e\ge \frac{13}{16},{\sum }_j{\mathbb{E}}_0{N}_j\le \frac{51}{100}T\mathrm{.}$ For the last assertion $SA\ge 100$ gives $1\mathrm{/}(2pT)\le 3\mathrm{/}1600<1\mathrm{/}100$. Applying the testing calculation and averaging over $j$ gives, with $m=51\mathrm{/}100$, $\frac{1}{K}{\sum }_j{\mathbb{E}}_j{N}_j\le \frac{mT}{K}+\frac{Te}{2\sqrt{p(1-p-e)}}\sqrt{\frac{mT}{K}}\mathrm{.}$ Set $c=7\mathrm{/}20$ and $L=\sqrt{KT\mathrm{/}p}$. Combining the preceding inequalities yields $\frac{1}{K}{\sum }_j{\mathbb{E}}_j[T{\rho }^{\ast }-R_T]\ge L(\frac{c}{4+2e\mathrm{/}p}-\frac{cm}{2K}-\frac{c^2}{4}\sqrt{\frac{m}{1-p-e}})\mathrm{.}$ Since $4+2e\mathrm{/}p\le 17\mathrm{/}4$ and $\sqrt{(51\mathrm{/}100)\mathrm{/}(13\mathrm{/}16)}<4\mathrm{/}5$, the coefficient is greater than $\frac{7}{85}-\frac{119}{40000}-\frac{49}{2000}=0.054877941\dots >\frac{1}{20}\mathrm{.}$ Therefore at least one $j$ satisfies ${\mathbb{E}}_j[T{\rho }^{\ast }-R_T]>\frac{1}{20}\sqrt{\frac{3D}{8}KT}\ge \frac{1}{20}\sqrt{\frac{35}{352}}\sqrt{DSAT}>0.015\sqrt{DSAT}\mathrm{.}$ The last coefficient is approximately $0.0157664$; alternatively square both positive sides to check it exactly.

Now suppose $1\le D<16$, the remaining allowed diameter range. The parameter condition gives $A\ge S^{20\mathrm{/}D}>S^{5\mathrm{/}4}$, so $S\mathrm{/}A<S^{-1\mathrm{/}4}\le {10}^{-1\mathrm{/}4}<3\mathrm{/}5$. Put $B=A-S+1$ and $K=SB$; then $B>(2\mathrm{/}5)A$ and $K>(2\mathrm{/}5)SA\ge 40$. At each of the $S$ states give one deterministic action to every other state, using $S-1$ actions, and $B$ distinct self-loop actions. All rewards in the baseline are independent Bernoulli variables of mean $1\mathrm{/}2$. For each of the $K$ self-loop pairs $j$, environment $M_j$ changes that pair's reward mean to $1\mathrm{/}2+e$, where $e=\frac{1}{5}\sqrt{K\mathrm{/}T}\le \frac{1}{5}\mathrm{.}$ The last inequality follows from $K\le SA\le T$ because $D\ge 1$. Rewards may be generated independently conditional on state-action history; transitions are the same deterministic transitions in all environments. Every environment has diameter one and exactly the required numbers of states and actions. Its optimal average reward is $1\mathrm{/}2+e$: no reward mean exceeds this, and the learner can reach the special state in at most one step and then repeatedly use its special self-loop. Start at any fixed state. Here the testing calculation gives $\mathrm{KL}(P_0\mathrm{\parallel }{P}_j)\le \frac{10}{3}{e}^2{\mathbb{E}}_0{N}_j,\frac{1}{K}{\sum }_j{\mathbb{E}}_j{N}_j\le \frac{T}{K}+Te\sqrt{\frac{5T}{3K}},$ because $1\mathrm{/}2-e\ge 3\mathrm{/}10$ and ${\sum }_j{\mathbb{E}}_0{N}_j\le T$. The expected regret in $M_j$ is exactly $e(T-{\mathbb{E}}_j{N}_j)$. Consequently $\frac{1}{K}{\sum }_j{\mathbb{E}}_j[T{\rho }^{\ast }-R_T]\ge \sqrt{KT}[\frac{1}{5}(1-\frac{1}{K})-\frac{1}{25}\sqrt{\frac{5}{3}}]>\frac{7}{50}\sqrt{KT}\mathrm{.}$ Indeed, $K\ge 40$ and $\sqrt{5\mathrm{/}3}<13\mathrm{/}10$ make the bracket at least $39\mathrm{/}200-13\mathrm{/}250=143\mathrm{/}1000>7\mathrm{/}50$. Thus at least one $j$ has regret greater than $(7\mathrm{/}50)\sqrt{(2\mathrm{/}5)SAT}$. Since $D<16$ and $(7\mathrm{/}50)\sqrt{2\mathrm{/}5}>0.06=4(0.015)$, this is greater than $0.015\sqrt{DSAT}$. Label the bad root in the large-diameter construction by the prescribed initial state; in the small-diameter construction any prescribed initial state works. Thus both branches prove the stated quantifiers.

Take $S=10$, $A={10}^{40}$, $D=1\mathrm{/}2$, and any integer $T\ge DSA$. These parameters satisfy $S,A\ge 10$ and $D=20{\log }_{A}S$. For any two distinct states $x,y$, the hitting time ${\tau }_y$ from $x$ is at least one on every path, so its expectation under every policy is at least one. Thus every ten-state communicating MDP has raw diameter at least one, and [F2] also makes its normalized diameter at least one.

No MDP with the required state count has diameter at most $1\mathrm{/}2$. Consequently the existential MDP in the original planned statement does not exist for the admissible parameters of step 7.1, regardless of the algorithm or the constant. This refutes the exact original statement. Its phrase “some MDP ... every learning algorithm” additionally reverses the minimax quantifiers: the proof above establishes an MDP chosen after the learning rule, not a single environment hard for all rules.