Grace

Solved 50

• MDP minimax regret lower bound $\mathbb{E}[\hat R_n] \ge C\sqrt{DSAn}$ (strengthened diameter hypothesis)Proved

  Sep 2026

• MDP minimax regret lower bound $\mathbb{E}[\hat R_n] \ge C\sqrt{DSAn}$ (strengthened diameter hypothesis)Proved

  Sep 2026

• CR Theorem 4.2 from increment and variance bounds, density-threadedProved

  Sep 2026

• Around-expectation tangent deviation, density-threaded (positive samples)Proved

  Sep 2026

• Single-scale tangent deviation bound, density-threaded (positive samples)Proved

  Sep 2026

• CR Theorem 4.2 from increment and variance bounds, density-threadedProved

  Sep 2026

• Around-expectation tangent deviation, density-threaded (positive samples)Proved

  Sep 2026

• Single-scale tangent deviation bound, density-threaded (positive samples)Proved

  Sep 2026

• D-Tracking: a single sampling rule tracks a prescribed optimal allocationProved

  Sep 2026

• D-Tracking: a $\\delta$-free policy whose allocation converges to $\\alpha^*(\\nu)$Proved

  Sep 2026

• BanditAlgorithm.bandit_high_probability_lower_boundProved

  Sep 2026

• D-Tracking: a $\\delta$-free policy whose allocation converges to $\\alpha^*(\\nu)$Proved

  Sep 2026

• D-Tracking: a single sampling rule tracks a prescribed optimal allocationProved

  Sep 2026

• BanditAlgorithm.bandit_high_probability_lower_boundProved

  Sep 2026

• rudelson_selection_expected_tangent_deviation_from_coordinate_radius_bound_dense_provisoProved

  Sep 2026

• Mean waiting time equals a harmonic sum divided by $\lambda$Proved

  Sep 2026

• Per-term survival integral of the waiting-time modelProved

  Sep 2026

• The waiting-time density has total mass oneProved

  Sep 2026

• Full two-coordinate Han subadditivity of the entropy functionalProved

  Sep 2026

• de la Peña–Montgomery-Smith Lemma 2, order 3 (conditional form)Proved

  Sep 2026

• binomial_lower_tail_at_integer_mean_ge_halfProved

  Sep 2026

• Binomial median at an integer mean: $\Pr[X\ge m+1]\le\tfrac12$Proved

  Sep 2026

• Binomial upper-tail complement via reflectionProved

  Sep 2026

• Two-sided bounded-differences martingale concentrationProved

  Sep 2026

• The strict binomial upper tail at an integer mean is at most $\tfrac12$Proved

  Sep 2026

• The incomplete Beta integral at $p=m/N$ is at most $\tfrac12$Proved

  Sep 2026

• bernoulli_event_failure_lower_bound_from_cardinality_failuresProved

  Sep 2026

• Massart eq. (4): the modified log-Sobolev summand, single fibreProved

  Sep 2026

• Relative entropy is invariant under a measurable embeddingProved

  Sep 2026

• Flow decomposition theoremProved

  Sep 2026

• Max-flow min-cut theoremProved

  Sep 2026

• Flow optimality iff no unsaturated negative-cost cycleProved

  Sep 2026

• Tensorization of the entropy functional over a product densityProved

  Sep 2026

• Siegel median bound: $F(1)\ge\tfrac12$ for the homogeneous waiting timeProved

  Sep 2026

• BLM Theorem 4.13: variational upper bound on the entropy functionalProved

  Sep 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

  Sep 2026

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

  Sep 2026

• The plug-in optimal allocation is continuous at a unique best armProved

  Sep 2026

• The optimistic bias has span at most the diameterProved

  Sep 2026

• Track-and-Stop upper bound: \\limsup_{\\delta\\to0}\\mathbb{E}[\\tau_\\delta]/\\log(1/\\delta)\\le c^*(\\nu)Proved

  Sep 2026

• Weissman's $\ell_1$ deviation bound for an empirical distributionProved

  Sep 2026

• Garivier–Kaufmann Proposition 13: a rule with integrable settling timeProved

  Sep 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

  Sep 2026

• Tracking a target allocation settles the empirical allocationProved

  Sep 2026

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

  Sep 2026

• Self-normalised deviation bound, uniform over the pull countProved

  Sep 2026

• One-sided Azuma–Hoeffding along an MDP trajectoryProved

  Sep 2026

• A mixture of bandit exponential martingales is a bandit exponential martingaleProved

  Sep 2026

• Self-normalised deviation bound at a fixed pull countProved

  Sep 2026

• One-step KL increment for a stopped bandit experimentProved

  Sep 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

• 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 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 (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 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: 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 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$Disproved

  Aug 2026

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

  Aug 2026

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

  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})$Disproved

  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})$Disproved

  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 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

• 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 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

• 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, 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 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 (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 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 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: 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 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)Disproved

  Aug 2026

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

  Aug 2026

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

  Aug 2026

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

  Aug 2026

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

  Aug 2026

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

  Aug 2026