Pith. sign in

REVIEW 2 minor 12 references

Without bias-function bounds, algorithms that rarely switch arms incur super-logarithmic regret in Markovian bandits with hidden states, yet UCB-NOM recovers O(log T) regret when the bounds are supplied.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-06-29 01:18 UTC pith:DAZ6TTNI

load-bearing objection The paper carves out self-degrading Markovian bandits where non-observability is mild and UCB-NOM gets state-independent nearly-log regret under a pure-policy benchmark.

arxiv 2606.27448 v1 pith:DAZ6TTNI submitted 2026-06-25 cs.LG

Learning in Markovian bandits with non-observable states and constrained decision epochs

Thomas Hira , Victor Boone , Urtzi Ayesta , Ina Maria Verloop This is my paper
classification cs.LG
keywords Markovian banditsnon-observable statesregret minimizationUCB algorithmpure policiesself-degrading banditsconstrained decision epochs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines regret minimization for Markovian bandits whose internal states remain hidden from the learner and whose decision epochs may be constrained. It introduces self-degrading Markovian bandits, a class generalizing rested bandits in which any optimal long-run policy simply selects one arm at the outset and never switches. The central finding is that any algorithm forced to switch arms only infrequently must suffer regret growing faster than log T for every such bandit unless it is given a prior bound on the arms' bias functions. The authors construct UCB-NOM, an optimistic index rule, that attains nearly logarithmic regret without the bound and exact O(log T) regret once the bound is supplied, with all guarantees independent of the number of states per arm.

Core claim

In self-degrading Markovian bandits with non-observable states, pure policies that pick one arm and never switch are asymptotically optimal. Without prior knowledge, the regret of any rarely-switching algorithm necessarily scales as ω(log T). UCB-NOM achieves nearly logarithmic regret in general and O(log T) regret when supplied with bounds on the bias functions, together with an O(√T log T) worst-case bound; none of these bounds depend on the number of states.

What carries the argument

UCB-NOM, an optimistic index algorithm that constructs upper confidence bounds on arm performance without ever observing states and compares against the best fixed-arm pure policy.

Load-bearing premise

The analysis requires that the bandit belongs to the self-degrading class in which a single fixed arm remains optimal forever.

What would settle it

A concrete self-degrading bandit instance together with a rarely-switching algorithm that nevertheless attains O(log T) regret without any supplied bound on the bias functions.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The manuscript studies regret minimization in Markovian bandits with non-observable states and possibly constrained decision epochs. It restricts attention to a pure regret benchmark against the best fixed-arm pure policy. The authors introduce the class of self-degrading Markovian bandits (a generalization of rested Markovian bandits) in which pure policies are asymptotically optimal. They prove that, without prior knowledge, any algorithm that switches arms rarely must incur ω(log T) regret on every such bandit. They propose the optimistic algorithm UCB-NOM, which achieves nearly logarithmic regret in the no-prior-knowledge regime. With prior knowledge in the form of a bound on the bias functions, a suitable instantiation of UCB-NOM attains O(log T) regret together with an O(√(T log T)) worst-case bound; all stated bounds are independent of the number of states.

Significance. If the derivations hold, the work demonstrates that non-observability of states is a mild inconvenience within the self-degrading class, yielding regret bounds that do not scale with state cardinality. The explicit separation of the no-prior-knowledge regime (where logarithmic regret is impossible for rare-switching policies but nearly achievable) from the known-bias regime is a clear contribution. Credit is due for the model definition that enables state-independent bounds and for the concrete algorithmic instantiation that realizes the improved rates.

minor comments (2)
  1. [§1] The abstract and title mention constrained decision epochs, yet the main regret statements focus on the non-observability aspect; a short paragraph in §1 clarifying whether the bounds continue to hold under epoch constraints would improve readability.
  2. [§2] Notation for the bias functions and the self-degrading condition is introduced without an explicit comparison table to the standard rested-bandit setting; adding such a comparison would help readers verify the claimed generalization.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, accurate summary of our contributions on self-degrading Markovian bandits and UCB-NOM, and recommendation for minor revision. We appreciate the recognition that non-observability is a mild inconvenience within this class and that the separation of regimes is a clear contribution.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper defines a new problem class (self-degrading Markovian bandits) and restricts the benchmark to pure regret against pure policies that never switch. Within this explicitly delimited setting, it derives regret bounds for UCB-NOM that hold independently of state cardinality and that distinguish the no-prior-knowledge case (nearly logarithmic) from the known-bias case (logarithmic). No load-bearing step reduces by construction to a fitted parameter, a self-citation chain, or a renaming of an input; the central claims are direct consequences of the model definitions and the algorithm's optimistic construction, making the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 1 invented entities

Abstract only; no explicit free parameters, axioms, or invented entities beyond the new bandit class definition are detailed. The self-degrading class is presented as a generalization without independent evidence provided.

invented entities (1)
  • self-degrading Markovian bandits no independent evidence
    purpose: Generalization of rested Markovian bandits where pure policies are asymptotically optimal
    New class introduced to make pure policies optimal; no external validation mentioned.

pith-pipeline@v0.9.1-grok · 5819 in / 1326 out tokens · 39410 ms · 2026-06-29T01:18:09.697986+00:00 · methodology

0 comments
read the original abstract

This paper studies the problem of regret minimization in Markovian bandits with \emph{non-observable states} and possibly \emph{constrained} decision epochs. The focus is restricted to a ``pure'' regret benchmark, that compares the performance of the learning algorithm to the best \emph{pure policy} which -- akin to optimal policies of stochastic bandits -- picks the optimal arm from start to finish without ever switching. We introduce a generalization of rested Markovian bandits, \emph{self-degrading Markovian bandits}, for which pure policies are always asymptotically optimal.We show that without prior knowledge on the underlying bandit, the regret of algorithms that switch arms rarely necessarily scales super-logarithmically for every bandit, i.e., as $\omega(\log(T))$, where $T$ is the learning horizon. Despite the unreachability of the logarithmic regime, we design UCB-NOM, an optimistic algorithm inspired by UCB, of which the regret is nearly logarithmic. Lastly, we show that given prior knowledge on the Markovian bandit in the form of a bound on the bias functions of its arm, a proper instantiation of UCB-NOM achieves $O(\log(T))$ regret. We further show that this prior knowledge allows for a $O(\sqrt{T \log(T)})$ worst-case regret bound for UCB-NOM. Notably, our regret bounds do not depend on the number of states of the underlying Markov chains. Our findings suggest that the non-observability of states is a mild inconvenience in self-degrading Markovian bandits.

Figures

Figures reproduced from arXiv: 2606.27448 by Ina Maria Verloop, Thomas Hira, Urtzi Ayesta, Victor Boone.

Figure 1
Figure 1. Figure 1: An arm that requires to be activated at least [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A Gilbert-Elliott channel with parameters [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An instance of Nerlove-Arrow toy model. In human resources or advertisement, skill or goodwill is earned by investing effort into it. When a high quantity is accumulated, more reward is earned. But when abandoned, those fade away. This idea can be 4This choice of initial state is made for simplicity. The channel is not self-degrading if initialized in state OFF, but it can be shown that it satisfies the se… view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of the transformation Mε a . More precisely, we show that E M,Λ [Na(T)] ≥ 1 ε log(T). Since ε > 0 is arbitrary, we deduce that E M,Λ [Na(T)] = ω(log(T)), which directly lower bounds the expected pseudo-regret. Equation (7) now follows by linking the pseudo-regret to the regret using the ψ-rarely switching property (Proposition 1). 4.2 An indexed optimistic algorithm: UCB-NOM In this Section… view at source ↗
Figure 5
Figure 5. Figure 5: Regret of UCB-NOM(D) on a Markovian bandits with two arms. The first arm a = 1 is a stochastic bandit with reward ν1 = Bernoulli(0.3). The second arm a = 2 is a two states Markovian arm whose transition are, when active, uniform over {0, 1}, and when passive, deterministically directed to 0. Associated rewards are ν2(0) = 0 and ν2(1) = Bernoulli(0.8). In the bonus, the term due to switching cost cannot be … view at source ↗
Figure 6
Figure 6. Figure 6: The precise statement is given below. 31 [PITH_FULL_IMAGE:figures/full_fig_p031_6.png] view at source ↗
Figure 6
Figure 6. Figure 6: An illustration of the transformation Mε a . Lemma C.4 (Idealistic state transform). Let M ≡ (S, ν, p) a Markov reward process12 with [0, 1]-rewards. For all ε > 0, there exists a Markov reward process Mε ≡ (S + {s∞}, νε , pε ) such that max s∈S {KL(ν(s)||ν ε (s)) + KL(p(s)||p ε (s))} ≤ ε with [0, 1]-rewards, g∗(Mε ) = 1 and sp(b ∗ (Mε )) ≤ 2/ε. Proof. Let ε > 0. Add an extra state s∞ to M. In Mε ≡ (S + {s… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 3 canonical work pages

  1. [1]

    neurips.cc/paper_files/paper/2019/file/88fee0421317424e4469f33a48f50cb0-Paper.pdf

    URLhttps://proceedings. neurips.cc/paper_files/paper/2019/file/88fee0421317424e4469f33a48f50cb0-Paper.pdf. Victor Boone. Optimal regrets in markov decision processes, November

    2019

  2. [2]

    Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi

    URLhttps://arxiv.org/abs/2501.13013. Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. Tightening Exploration in Upper Confidence Reinforcement Learning. In Hal Daumé III and Aarti Singh (eds.),Proceedings of the 37th International Conference on Machine Learning, volume 119 ofProceedings of Machine Learning Research, pp. 1056–1066. PMLR, July

    work page arXiv

  3. [3]

    Thompson sampling in non-episodic restless bandits

    Young Hun Jung, Marc Abeille, and Ambuj Tewari. Thompson sampling in non-episodic restless bandits. arXiv preprint arXiv:1910.05654,

    work page arXiv 1910

  4. [4]

    Logarithmic weak regret of non-bayesian restless multi-armed bandit

    Haoyang Liu, Keqin Liu, and Qing Zhao. Logarithmic weak regret of non-bayesian restless multi-armed bandit. In2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1968–1971. IEEE,

    1968

  5. [5]

    Learning in a changing world: Restless multiarmed bandit with unknown dynamics.IEEE Transactions on Information Theory, 59(3):1902–1916,

    Haoyang Liu, Keqin Liu, and Qing Zhao. Learning in a changing world: Restless multiarmed bandit with unknown dynamics.IEEE Transactions on Information Theory, 59(3):1902–1916,

    1902

  6. [6]

    Near sample-optimal reduction-based policy learning for average reward mdp.arXiv preprint arXiv:2212.00603,

    Jinghan Wang, Mengdi Wang, and Lin F Yang. Near sample-optimal reduction-based policy learning for average reward mdp.arXiv preprint arXiv:2212.00603,

    work page arXiv

  7. [7]

    As a direct consequence of Lemma A.1, the regret can be approximated by ∑T−1 t=1 (g∗−R(t)), where g∗= maxa∈Aga

    ] −(T−1)ga =E M,π [T−1∑ t=1 (R(t+ 1)−ga) ] °1 =    EM,π [∑T−1 t=1 (R(t+ 1)−ra(Sa(t))) ] +EM,π [∑T−1 t=1 (ba(Sa(t))−ba(Sa(t+ 1))) ] +EM,π [∑T−1 t=1 ( ba(Sa(t+ 1))−p1 a(Sa(t))ba )] °2 =E M,π[ba(Sa(1))−ba(Sa(T))], where (°1) follows from the Poisson equation ofπ≡πa; and (°2) uses that the first and third terms in (°1) are martingale difference seque...

    2009

  8. [8]

    Using a change of measure (Appendix C.1, see Theorems C.1 and C.2), we can bind the behavior of the learning algorithm inM1 to its behavior onM2

    The core of the argument consists in finding two instancesM1 andM2 that (1) are difficult to distinguish from a statistical view points and (2) do not have the same optimal arm. Using a change of measure (Appendix C.1, see Theorems C.1 and C.2), we can bind the behavior of the learning algorithm inM1 to its behavior onM2. Then, the consistency of the algo...

    1979

  9. [9]

    31 Initial, trueMa Ma Possible alternativeMε a Mε a s∞ ε R= 1 Figure 6: An illustration of the transformationMε a

    The precise statement is given below. 31 Initial, trueMa Ma Possible alternativeMε a Mε a s∞ ε R= 1 Figure 6: An illustration of the transformationMε a. Lemma C.4(Idealistic state transform).Let M≡(S,ν,p)a Markov reward process12 with[0 , 1]-rewards. For allε>0, there exists a Markov reward processMε≡(S+{s∞},νε,pε)such that max s∈S {KL(ν(s)||νε(s)) + KL(p...

    2025

  10. [10]

    Late bloomers (IV).This term is almost surely0. Indeed, when term(IV) = 1we have ˜ga∗(ta ℓ)−˜ga(ta l ) °1 ≥ga∗−ε−(ˆga(ta ℓ) +ξ(ta ℓ,δ(ta ℓ)) °2 ≥ga∗−ga−2ε−ξ(ta ℓ,δ(ta ℓ)) °3 >0, where (°1) follow fromga∗≤˜ga∗(ta ℓ) +ε; (°2) fromˆga(ta ℓ)≤ga +ε; and (°3) fromNa(ta ℓ)>χε(T ). Thus, by definition, the algorithm will not select armaat timeta ℓ. Bounding the v...

    2010

  11. [11]

    The dominant termC0 b √ |A|Tlog(T)scales exclusively with the span bound

    scales with the number of episodes as a second order term. The dominant termC0 b √ |A|Tlog(T)scales exclusively with the span bound. Because the span boundC0 b is to be analogous to a diameter-like quantityD, this term is to be compared with the famousD|S| √ |A|Tlog(T)regret bound of UCRL2 (Auer et al. (2009)), for which the dependency inDrather than √ Di...

    2009

  12. [12]

    Optimism overshot (III).This term is the dominant one. We start by writing it as follows: E   ∞∑ k=1 t′ k+1−1∑ t=t′ k (III)   °1 =E   ∞∑ k=1 (t′ k+1−t′ k)·C0 b   √ 1 NA(t′ k)(t′ k) log ( 1 +NA(t′ k)(t′ k) δ(t′ k) ) + log ( 1 +NA(t′ k)(t′ k) ) NA(t′ k)(t′ k)     (D.24) °2 ≤E [ ∞∑ k=1 1(tk≤T)(tk+1−tk)·C0 b (√ 1 NA(t′ k)(t′ k) log (1 +T δ(T) )...

    1963

This paper was first reviewed by grok-4.3 on June 29, 2026.