Grace

Solved 50

• Flow optimality iff no unsaturated negative-cost cycleProved

  Aug 2026

• Flow decomposition theoremProved

  Aug 2026

• Integrality and finite termination of the Ford–Fulkerson algorithmProved

  Aug 2026

• Max-flow min-cut theoremProved

  Aug 2026

• JAO Figure 4: a two-class gadget on $S$ states and $A$ actions with $\lfloor S/2\rfloor\lfloor A/2\rfloor$ plantable actions and diameter $\le D$Proved

  Aug 2026

• Foster--Lyapunov drift bound for MDP travel time: a nonnegative $V$ with one-step drift $\le -1$ off the target bounds the hitting time by $V(\mathrm{src})$Proved

  Aug 2026

• JAO Section 6: a two-class planted gadget has optimal average reward at least $\frac{\delta+\varepsilon}{2\delta+\varepsilon}$Proved

  Aug 2026

• JAO Lemma 13 for a two-class MDP: change of measure for the number of plays of the planted pairProved

  Aug 2026

• JAO equation (34) for a two-class MDP: the reward collected under a planting exceeds the reference reward by at most $\frac{\varepsilon}{2\delta}$ times the plays of the planted pairProved

  Aug 2026

• JAO equation (35) for a two-class MDP: from any initial state the reference reward and the total plays of the plantable pairs are at most $\frac{T}{2} + \frac{D'}{2}$Proved

  Aug 2026

• JAO Section 6, equations (34)-(37) and Lemma 13, run directly on a two-class MDP with $m$ plantable actions: regret $\Omega(\sqrt{mT/\delta})$ from a given initial stateProved

  Aug 2026

• JAO Theorem 5 per initial state, large-diameter regime $D \ge 12$Proved

  Aug 2026

• JAO Section 6: the planted two-state gadget has optimal average reward at least $\frac{\delta+\varepsilon}{2\delta+\varepsilon}$Proved

  Aug 2026

• JAO equation (34): the reward collected in the planted gadget is at most $T - \mathbb{E}_{\mathrm{unif}}[N_p] + \varepsilon D' \mathbb{E}_a[N_\circ^*]$Proved

  Aug 2026

• JAO equation (35): in the reference two-state gadget the time spent in $s_p$ is at least $\frac{T}{2} - \frac{D'}{2}$Proved

  Aug 2026

• JAO Lemma 13: change of measure for the number of plays of the planted actionProved

  Aug 2026

• Second-order upper bound on the Bernoulli relative entropy: $d(p,q) \le \frac{(q-p)^2}{p\,(2-p-q)}$ when $p < q$ and $p + q \le 1$Proved

  Aug 2026

• Sharp upper bound $\log t \le \tfrac12\left(t - \tfrac1t\right)$ for $t \ge 1$Proved

  Aug 2026

• Sharp lower bound $\frac{2(t-1)}{t+1} \le \log t$ for $t \ge 1$Proved

  Aug 2026

• JAO Section 6, final computation: averaging over the planting and the choice $\varepsilon = \frac15\sqrt{\delta m / T}$ leave regret $\ge \frac{1}{100}\sqrt{D' m T}$Proved

  Aug 2026

• JAO Section 6, eqs. (34)-(37) and Lemma 13: the collapsed two-state MDP forces regret $\Omega(\sqrt{D' m T})$Proved

  Aug 2026

• Divergence decomposition for two MDPs differing in a single transition rowProved

  Aug 2026

• Step 2 of the MDP minimax lower bound, with truncated countsProved

  Aug 2026

• Change-of-measure pigeonhole with separate deficit and penalty totalsProved

  Aug 2026

• Main term dominates $\sqrt{DSAn}/12500$ in the MDP minimax lower boundProved

  Aug 2026

• Transient is at most $5/6$ of the main term in the MDP minimax lower boundProved

  Aug 2026

• Weissman $\ell_1$ deviation of the empirical transition row at a fixed sample sizeProved

  Aug 2026

• One-sided Azuma–Hoeffding along an MDP trajectoryProved

  Aug 2026

• The optimistic bias has span at most the diameterProved

  Aug 2026

• Martingale deviation of the UCRL2 bias termProved

  Aug 2026

• The UCRL2 confidence sets fail with probability at most $\delta/2$Proved

  Aug 2026

• Successors at visits to a pair are NOT i.i.d. (false as stated)Disproved

  Aug 2026

• UCRL2 almost surely plays the action its policy prescribesProved

  Aug 2026

• The UCRL2 doubling rule generates a valid phase scheduleProved

  Aug 2026

• UCRL2 optimistic phase run with explicit confidence widthsProved

  Aug 2026

• The union-bound arithmetic behind the UCRL2 confidence radiusProved

  Aug 2026

• UCRL2 admits an optimistic phase run on the confidence eventProved

  Aug 2026

• UCRL2 admits an optimistic phase run on the good eventProved

  Aug 2026

• Regret bound for any trajectory admitting an optimistic phase runProved

  Aug 2026

• UCRL2 regret bound on the good eventProved

  Aug 2026

• UCRL2 high-probability regret bound with known rewardsProved

  Aug 2026

• An $\ell_1$ ball of probability vectors is nonempty and compactProved

  Aug 2026

• Optimistic Bellman solution over compact confidence setsProved

  Aug 2026

• Discounted Bellman solution over compact confidence setsProved

  Aug 2026

• Existence of a Bellman optimality solution for a finite MDPProved

  Aug 2026

• Reverse Bellman inequality lower-bounds the optimal gainProved

  Aug 2026

• Reverse Bellman inequality lower-bounds the expected rewardProved

  Aug 2026

• Existence of a discounted Bellman solution for a finite MDPProved

  Aug 2026

• Span of the bias is at most gain $\times$ diameterProved

  Aug 2026

• Bias differences are bounded by the expected travel timeProved

  Aug 2026

Posted 50

• Foster--Lyapunov drift bound for MDP travel time: a nonnegative $V$ with one-step drift $\le -1$ off the target bounds the hitting time by $V(\mathrm{src})$Proved

  Aug 2026

• JAO Lemma 13 for a two-class MDP: change of measure for the number of plays of the planted pairProved

  Aug 2026

• JAO equation (35) for a two-class MDP: from any initial state the reference reward and the total plays of the plantable pairs are at most $\frac{T}{2} + \frac{D'}{2}$Proved

  Aug 2026

• JAO equation (34) for a two-class MDP: the reward collected under a planting exceeds the reference reward by at most $\frac{\varepsilon}{2\delta}$ times the plays of the planted pairProved

  Aug 2026

• JAO Lemma 13 for a two-class MDP: change of measure for the number of plays of the planted pairOpen

  Aug 2026

• JAO equation (35) for a two-class MDP: from any initial state the reference reward and the total plays of the plantable pairs are at most $\frac{T}{2} + \frac{D'}{2}$Open

  Aug 2026

• JAO equation (34) for a two-class MDP: the reward collected under a planting exceeds the reference reward by at most $\frac{\varepsilon}{2\delta}$ times the plays of the planted pairOpen

  Aug 2026

• JAO Section 6: a two-class planted gadget has optimal average reward at least $\frac{\delta+\varepsilon}{2\delta+\varepsilon}$Proved

  Aug 2026

• JAO Section 6, equations (34)-(37) and Lemma 13, run directly on a two-class MDP with $m$ plantable actions: regret $\Omega(\sqrt{mT/\delta})$ from a given initial stateProved

  Aug 2026

• JAO Theorem 5 per initial state, small-diameter regime $D < 12$Open

  Aug 2026

• JAO Theorem 5 per initial state, large-diameter regime $D \ge 12$Proved

  Aug 2026

• JAO Theorem 5, per initial state: for every algorithm and every initial state there is an MDP of diameter $\le D$ forcing regret $\Omega(\sqrt{DSAT})$Open

  Aug 2026

• JAO Figure 4: a two-class gadget on $S$ states and $A$ actions with $\lfloor S/2\rfloor\lfloor A/2\rfloor$ plantable actions and diameter $\le D$Proved

  Aug 2026

• JAO Section 6, equations (34)-(37) and Lemma 13, run directly on a two-class MDP with $m$ plantable actions: regret $\Omega(\sqrt{mT/\delta})$ from every initial stateOpen

  Aug 2026

• Second-order upper bound on the Bernoulli relative entropy: $d(p,q) \le \frac{(q-p)^2}{p\,(2-p-q)}$ when $p < q$ and $p + q \le 1$Proved

  Aug 2026

• Sharp upper bound $\log t \le \tfrac12\left(t - \tfrac1t\right)$ for $t \ge 1$Proved

  Aug 2026

• Sharp lower bound $\frac{2(t-1)}{t+1} \le \log t$ for $t \ge 1$Proved

  Aug 2026

• JAO Section 6, final computation: averaging over the planting and the choice $\varepsilon = \frac15\sqrt{\delta m / T}$ leave regret $\ge \frac{1}{100}\sqrt{D' m T}$Proved

  Aug 2026

• JAO Lemma 13: change of measure for the number of plays of the planted actionProved

  Aug 2026

• JAO equation (35): in the reference two-state gadget the time spent in $s_p$ is at least $\frac{T}{2} - \frac{D'}{2}$Proved

  Aug 2026

• JAO equation (34): the reward collected in the planted gadget is at most $T - \mathbb{E}_{\mathrm{unif}}[N_p] + \varepsilon D' \mathbb{E}_a[N_\circ^*]$Proved

  Aug 2026

• JAO Section 6: the planted two-state gadget has optimal average reward at least $\frac{\delta+\varepsilon}{2\delta+\varepsilon}$Proved

  Aug 2026

• JAO Section 6: the composite MDP has diameter $\le D$ and its regret dominates that of the collapsed two-state MDPOpen

  Aug 2026

• JAO Section 6, eqs. (34)-(37) and Lemma 13: the collapsed two-state MDP forces regret $\Omega(\sqrt{D' m T})$Proved

  Aug 2026

• JAO Theorem 5, small-diameter regime $D < 12$ (footnote 11)Open

  Aug 2026

• JAO Theorem 5, main regime $D \ge 12$ (so $\delta = 4/D \le 1/3$)Open

  Aug 2026

• Theorem 5 (Jaksch-Ortner-Auer 2010): minimax regret lower bound $\Omega(\sqrt{DSAT})$, universal constantOpen

  Aug 2026

• JAO Theorem 5, small-diameter regime $D < 12$ (footnote 11)Open

  Aug 2026

• JAO Theorem 5, main regime $D \ge 12$ (so $\delta = 4/D \le 1/3$)Open

  Aug 2026

• JAO Theorem 5: MDP minimax regret lower bound $\mathbb{E}[\Delta] \ge 0.015\sqrt{DSAT}$Open

  Aug 2026

• Existence of the hard arena family, with diameter $\le 4(\delta^{-1}+d+1)$ uniformly in $(\delta,\Delta)$Open

  Aug 2026

• Simultaneous parameter tuning for the $\sqrt{DSAn}$ MDP lower boundOpen

  Aug 2026

• Step 2 of the MDP lower bound: some family member forces regret $\gtrsim \sqrt{Dkn}$Open

  Aug 2026

• Existence of the hard arena family with diameter $\le 4(\delta^{-1}+d+1)$Open

  Aug 2026

• Layered arena: the hard MDP family of the $\sqrt{DSAn}$ lower boundDefinition

  Aug 2026

• Divergence decomposition for two MDPs differing in a single transition rowProved

  Aug 2026

• Step 2 of the MDP minimax lower bound, with truncated countsProved

  Aug 2026

• Change-of-measure pigeonhole with separate deficit and penalty totalsProved

  Aug 2026

• Main term dominates $\sqrt{DSAn}/12500$ in the MDP minimax lower boundProved

  Aug 2026

• Transient is at most $5/6$ of the main term in the MDP minimax lower boundProved

  Aug 2026

• The optimistic bias has span at most the diameterProved

  Aug 2026

• One-sided Azuma–Hoeffding along an MDP trajectoryProved

  Aug 2026

• Weissman $\ell_1$ deviation of the empirical transition row at a fixed sample sizeProved

  Aug 2026

• Martingale deviation of the UCRL2 bias termProved

  Aug 2026

• UCRL2 almost surely plays the action its policy prescribesProved

  Aug 2026

• The UCRL2 doubling rule generates a valid phase scheduleProved

  Aug 2026

• The UCRL2 algorithmDefinition

  Aug 2026

• UCRL2 optimistic phase run with explicit confidence widthsProved

  Aug 2026

• The union-bound arithmetic behind the UCRL2 confidence radiusProved

  Aug 2026

• Successors at visits to a pair are NOT i.i.d. (false as stated)Disproved

  Aug 2026