Data-Dependent Regret Bounds for Constrained MABs

Alberto Marchesi; Francesco Emanuele Stradi; Gianmarco Genalti; Matteo Castiglioni; Nicola Gatti

REVIEW 2 major objections 4 minor 21 references

Data-Dependent Regret Bounds for Constrained MABs

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper claims that constrained multi-armed bandits with hard per-round constraints admit data-dependent regret bounds, split into a Safety Complexity term and a Bandit Complexity term, with a matching lower bound.

desk verdict Genuinely new and worth refereeing, but Theorem 4 as stated is not proven: the proof silently drops a K/ρ^6 term that can dominate the advertised bound unless ρ is bounded below by a constant. read the letter →

arxiv 2505.20010 v2 pith:JUDPBYBV submitted 2025-05-26 cs.LG

Gianmarco Genalti , Francesco Emanuele Stradi , Matteo Castiglioni , Alberto Marchesi , Nicola Gatti This is my paper · ORCID

classification cs.LG

keywords constrainedmulti-armedbanditshardconstraintsdata-dependentregretboundssmall-losssafeexplorationlog-barrierOMDadversariallossesstochastic

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Constrained multi-armed bandits with hard constraints—where every round's decision must satisfy stochastic resource constraints with high probability—have so far been analyzed only through worst-case $\widetilde{O}(\sqrt{T})$ regret bounds. This paper asks whether regret can instead depend on the actual loss sequence, and answers yes when losses are adversarial and constraints are stochastic. Its algorithm, SOLB, achieves high-probability regret roughly $\frac{K\ln(1/\delta)}{\rho}\sqrt{\sum_{t=1}^T(\ell_t^\top(x^\diamond-x^*))^2}+\frac{1}{\rho}\sqrt{K\sum_{t=1}^T\ell_t^\top x^*\ln(1/\delta)}$, where $x^*$ is the best-in-hindsight feasible strategy and $x^\diamond$ is a known strictly feasible fallback. The first term, Safety Complexity, measures how far the fallback is from the optimum in loss space, while the second, Bandit Complexity, recovers the unconstrained small-loss rate; a lower bound shows both are inherent. If correct, regret on easy instances can be far below $\sqrt{T}$ while remaining equivalent to it in the worst case.

What carries the argument

The argument rides on a mix-and-project update. Each round, an OMD-with-log-barrier subroutine—online mirror descent with a log-barrier regularizer and action-dependent learning rates that grow when an arm's probability is too small—proposes a strategy $\tilde{x}_t$ in the truncated safe decision space $\tilde{S}_t=\Omega\cap S_t^\circ$, where $\Omega$ is the simplex truncated away from the boundary by $1/T$ and $S_t^\circ$ relaxes the estimated cost constraints by $K/T$. SOLB does not play $\tilde{x}_t$ directly; it plays $x_t=\gamma_{t-1}x^\diamond+(1-\gamma_{t-1})\tilde{x}_t$, with $\gamma_{t-1}\in[0,1]$ chosen from pessimistic cost estimates to pull the decision back toward the known strictly feasible $x^\diamond$ exactly when $\tilde{x}_t$ might violate a constraint. This identity splits regret into $R_T^\diamond=\sum_{t=1}^T\gamma_{t-1}\ell_t^\top(x^\diamond-x^*)$ plus $\tilde{R}_T=\sum_{t=1}^T(1-\gamma_{t-1})\ell_t^\top(\tilde{x}_t-x^*)$; Lemma 3 controls the first by the squared-loss distance between $x^\diamond$ and $x^*$, Lemma 4 controls the second through played and optimal losses, and substituting the tuned learning rate yields the two-term bound.

What would settle it

Simulate the four stochastic instances constructed in the proof of Theorem 5 with $K=3$, $T=10^4$, $\rho=0.1$, $\omega=0.1$, and $\Delta=0.1$: on the worse of instances $\nu_2$ and $\nu_3$, any randomized algorithm's average regret should be at least the claimed $\Omega(\Delta\sqrt{T}/\rho+\sqrt{\omega T})$ lower bound; falling below falsifies the lower bound, while SOLB exceeding the right-hand side of Equation (3) at confidence level $1-5\delta$ falsifies the upper bound.

Watch

Extended reading notes

Core claim

The central claim is that data-dependent regret is achievable under hard constraints that bind at every round with high probability. With adversarial losses and i.i.d. stochastic constraint costs, SOLB satisfies every constraint at every round with probability at least $1-\delta$ and, with probability at least $1-5\delta$, suffers regret $\widetilde{O}\big(\frac{K\ln(1/\delta)}{\rho}\sqrt{\sum_{t=1}^T(\ell_t^\top(x^\diamond-x^*))^2}+\frac{1}{\rho}\sqrt{K\sum_{t=1}^T\ell_t^\top x^*\ln(1/\delta)}\big)$. The Safety Complexity term vanishes when the optimal strategy is essentially the known safe fallback, and the Bandit Complexity term mirrors the small-loss lower bound of unconstrained adversarial bandits up to a $1/\rho$ factor. The matching lower bound over the constrained small-loss balls $B_{\omega,\Delta,T}$ shows that no algorithm can generally drop either dependence, so the two-term decomposition reflects the problem's structure rather than an artifact of the proof.

Load-bearing premise

The per-round safety guarantee and the two-term regret bound both presuppose that the learner is handed a strictly feasible strategy $x^\diamond$ together with its exact expected constraint costs $\theta_i$ and the resulting margin $\rho>0$; if that fallback or its exact costs are unavailable, the algorithm has no anchor to mix toward and the theorem's guarantees do not apply.

Editorial extensions

If this is right

In the best case—near-zero optimal loss or $x^*\approx x^\diamond$—the bound collapses toward the unconstrained small-loss rate, far below the $\widetilde{O}(\sqrt{T})$ typical of hard-constraint algorithms.
In the worst case, where both data-dependent sums scale linearly with $T$, the bound recovers the $\widetilde{O}(\sqrt{T})$-scale of prior hard-constraint results while exposing its two sources.
The lower bound tells algorithm designers that no method can make do with only one of the two terms: both the squared-loss gap to the fallback and the optimal cumulative loss are intrinsic to the problem.
Because the guarantee holds with high probability rather than only in expectation, the algorithm is usable in settings where rare constraint violations are unacceptable.
The soft-constraint warm-up delivers high-probability small-loss regret with sublinear cumulative violations, so the technique also applies when per-round safety is not required.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial extension: the Safety Complexity term depends on the chosen fallback $x^\diamond$, so a learner with several known feasible strategies could plausibly reduce regret by selecting the fallback that minimizes $\sum_{t=1}^T(\ell_t^\top(x^\diamond-x^*))^2$; the paper does not explore this selection problem.
Editorial extension: the paper leaves open whether the $1/\rho$ factor in Bandit Complexity can be removed; if a modified learning-rate schedule achieved that, hard constraints would pay only in the Safety Complexity term, which is what one might expect from the constraint layer alone.
Editorial extension: the $\gamma_t$-mixing construction transfers naturally to constrained linear bandits or constrained MDPs with a known safe policy, where the safe policy plays the role of $x^\diamond$; testing SOLB-style mixing there would extend the paper's scope.
Editorial extension: the constrained small-loss-ball parametrization by $(\omega,\Delta)$ offers a two-dimensional instance-complexity measure that could serve as a common yardstick for future safe online-learning algorithms.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Short version: this is a real contribution—first data-dependent regret bounds for constrained MABs—but the main theorem as printed isn't established. I checked the appendix; the stress-test concern holds up. In the proof of Theorem 4, the 55296 K ln(KTm/δ)/ρ^6 term from Lemma 3 appears on the first displayed line and then disappears into the final eO. That term is not a universal constant: the theorem allows ρ as small as 12K/T, which makes 1/ρ^6 scale like T^6. On sequences where both advertised terms are small, the dropped term dominates and the two-term decomposition is not proven. The qualitative claim that data-dependent bounds are achievable probably survives, but the statement needs amending—either keep the extra term or add a condition like ρ = Ω(1).

What's genuinely good: the hard-constraint algorithm SOLB is a clean construction. The adaptive γ_t mixing of the OMD proposal with a known strictly feasible strategy is exactly the right mechanism for per-round safety, and the Safety Complexity/Bandit Complexity split is a nice way to separate constraint difficulty from bandit learning. The lower bound is intricate: a four-instance construction with KL control and the forced play of the safe action gives the Δ/ρ√T term. That is substantive, careful work.

Soft spots, in proportion. First, the omitted ρ^6 term is load-bearing for the exact statement but likely repairable—requiring ρ bounded below by a constant makes the extra term absorbable and preserves the qualitative message. Second, the soft-constraint result, Theorem 2, is essentially Lee et al.'s OMD-with-log-barrier analysis applied to a safe decision set; the paper is honest about this, but the novelty there is limited. Third, the lower-bound proof has some compressed steps, particularly the transfer from stochastic instances to a fixed adversarial sequence in B_{ω,Δ,T}; the argument is sound in spirit but needs careful reading. Assumption 2 (knowing a strictly feasible strategy and its expected costs) is standard in this literature, not a flaw.

Read this if you work on safe/constrained bandits or small-loss bounds. It should go out to serious referees. The referee should require the authors to fix Theorem 4—by adding the K/ρ^6 term to the bound or by stating the ρ≥Ω(1) regime—before the central claims are taken at face value.

Referee Report

2 major / 4 minor

Summary. The paper studies multi-armed bandits with adversarial losses, stochastic constraint costs, and both soft and hard constraints. For soft constraints it proposes COLB, an OMD-with-log-barrier algorithm over truncated safe decision sets, and proves a high-probability small-loss regret bound of order O~(sqrt(K * sum_t ell_t^T x*)) with sublinear constraint violations. For hard constraints it proposes SOLB, which mixes the COLB iterate with a known strictly feasible strategy x^diamond using an adaptive combination factor. The main result, Theorem 4, claims a data-dependent regret bound consisting of a Safety Complexity term proportional to sqrt(sum_t (ell_t^T(x^diamond - x*))^2) and a Bandit Complexity term proportional to sqrt(K * sum_t ell_t^T x*). Theorem 5 gives a lower bound showing that both terms are necessary, up to the disclosed open question about the 1/rho factor in the Bandit Complexity term. The paper is a first treatment of data-dependent bounds in constrained MABs and contains detailed appendix proofs for both the soft- and hard-constraint results.

Significance. If Theorem 4 is established as stated, this is a meaningful contribution: it extends data-dependent small-loss bounds to constrained MABs, decomposes the regret into interpretable Safety and Bandit Complexity terms, and supports the decomposition with a lower-bound construction. The paper is careful in disclosing the known 1/rho gap between the upper and lower bounds and in generalizing Assumption 2 to the standard strictly-feasible-strategy assumption. The proof machinery is largely standard OMD/log-barrier analysis adapted to changing safe sets, and the appendix is substantial. However, the proof of the central theorem currently drops an additive term that can dominate in the parameter regime explicitly allowed by the theorem statement, so the exact advertised two-term bound is not established as written. The qualitative finding that data-dependent bounds are achievable in hard-constrained bandits may survive, but the precise statement and the tightness comparison in Section 5.3 need repair.

major comments (2)

The proof of Theorem 4 silently drops the additive K/rho^6 ln(KTm/delta) term that appears in Lemma 3. In the first displayed line of the proof, after combining Lemma 3 and Lemma 4, the term 55296 K ln(KTm/delta)/rho^6 is present; on the next line it is absorbed into the eO notation and never appears in the stated bound (3). The theorem's definition of eO says it hides only universal constants and logarithmic terms not depending on delta, and rho appears explicitly elsewhere in the bound, so K/rho^6 is not covered by that convention. Since the theorem allows rho as small as 12K/T, taking for example K=3 and rho=36/T makes the dropped term Theta(T^6), which dominates both displayed terms for loss sequences with small Safety and Bandit Complexity. Thus Eq. (3) is not established as written; the proof establishes at best the same expression plus an additive K/rho^6 ln(KTm/delta) term. Please amend the theorem statement, add a condition such as rho=Omega(1), or give a refined argument that removes the term, and revisit Corollary 1 and Section 5.3 accordingly.
The final step of the proof also omits additive K/eta and K eta ln(1/delta)/rho terms when solving the quadratic inequality in R_T. When L* = sum_t ell_t^T x* is zero and the Safety Complexity term is also zero, Eq. (3) displays a zero bound, while the proof still leaves an additive term of order K/rho times polylog(T, 1/delta) coming from K/eta with eta = rho/(40 H ln T ln(H/delta)). This term depends on rho and delta and is not covered by the stated eO convention. The exact two-term form in Eq. (3) is therefore stronger than what the proof delivers even after the rho^6 term is addressed. The theorem statement should either include these additive terms explicitly or define a precise convention stating which rho- and delta-dependent additive terms are hidden.

minor comments (4)

The lower-bound proof asserts that, to be safe with high probability, any algorithm must satisfy P(forall t: x_t(a3) >= epsilon/(epsilon+rho)) >= 1-delta under instance nu_1. This requirement is plausible and standard for confidence-interval-based safety, but it is stated without derivation from the paper's hard-constraint guarantee (Theorem 3). Please add a short argument showing how the confidence intervals and the Slater margin force this lower bound on the probability mass on a3.
The sentence 'SOLB achieves an optimal dependence on both Delta and omega' should be qualified: in the Bandit Complexity term the upper bound has a 1/rho factor while the lower bound does not, and the paper itself leaves removal of this factor as an open question. The claim is currently stated more strongly than what is proved.
There is a typo in 'optimal-in-hidsight' (should be 'hindsight'). Please also proofread the notation around eO in the abstract and Section 1, where the tilde symbol is repeatedly lost in rendering.
The definition of the combination factor gamma_t uses the condition E without explicitly recalling that E is evaluated under the clean event of Lemma 1; adding a sentence that the safety guarantee of Theorem 3 is conditional on E(delta) would improve clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the data-dependent regret terms are instance properties, and the algorithm's foundations and lower-bound tools are external.

full rationale

The paper's claimed derivation is self-contained rather than circular. Theorem 4 decomposes regret as RT = R⋄_T + eR_T using the identity xt = γt−1x⋄ + (1−γt−1)ext, then invokes Lemma 3 and Lemma 4, which bound these components by instance-dependent norms (Σ(ℓ_t^T(x⋄−x*))² and Σℓ_t^T x*) together with standard concentration arguments; neither lemma fits a parameter to data and then reports it as a prediction. The Slater strategy x⋄ and expected costs θi are algorithm inputs under Assumption 2, not fitted outputs, and the safety guarantee in Theorem 3 follows algebraically from the constructed mixing factor γt rather than from a fitted claim. The OMD-with-log-barrier engine and its high-probability martingale tools are cited to external work (Lee et al. 2020a; Jin et al. 2020), and the lower bound relies on external techniques (Gerchinovitz and Lattimore 2016; Auer et al. 2002). The self-citations (Bernasconi et al. 2022; Stradi et al. 2024a–e) occur in related-work positioning and tightness comparisons and are not load-bearing for the main upper bound. A reviewer-flagged issue—the absorption of the additive K ln(...)/ρ^6 term from Lemma 3 into the eO in the proof of Theorem 4—is a correctness gap in the stated two-term bound, not a circular reduction, since the displayed bound is not obtained by redefining its inputs but by an omitted error term.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data to manufacture the bound; the learning rate is chosen using the unknown optimal loss L* (standard, removable by doubling trick). The central assumptions are the standard Slater condition and the knowledge of a strictly feasible strategy, both common in hard-constraint bandits. No new entities are introduced.

free parameters (1)

learning rate η (for COLB and SOLB) = min{ρ/(40H ln T ln(H/δ)), sqrt(K / Σ_t ℓ_t^T x* ln(1/δ))} (analogous for COLB)
Set using the unknown cumulative loss of the optimal strategy L*; the paper cites a doubling trick to remove the need. This is standard for small-loss bounds, not a fit to the outcome, but it is a data-dependent tuning choice.

assumptions (4)

domain assumption Slater's condition: Program (1) admits a strictly feasible strategy x⋄ (Assumption 1).
Needed for hard-constraint guarantees; without a strictly feasible point, no algorithm can be safe while learning.
domain assumption Knowledge of a strictly feasible strategy x⋄ and its expected costs θ_i (Assumption 2).
SOLB takes x⋄ and θ_i as inputs; the combination factor γ_t is computed from them. This is stronger than typical assumptions in soft-constraint settings.
domain assumption Constraint costs are i.i.d. from fixed distributions Gi; losses are chosen adaptively by an adversary.
Statement in Section 2; needed for Lemma 1's concentration bounds and to avoid the Mannor et al. impossibility.
standard math Standard concentration inequalities (Hoeffding, Freedman, Azuma) and OMD log-barrier analysis from Lee et al. 2020a.
Used throughout the proofs; accepted external results.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Data-Dependent Regret Bounds for Constrained MABs." pith.science (2026). https://pith.science/paper/JUDPBYBV

@misc{pith2026250520010,
  author       = {Pith},
  title        = {Pith review of: Data-Dependent Regret Bounds for Constrained MABs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JUDPBYBV}},
  note         = {Machine review of arXiv:2505.20010}
}

abstract

This paper initiates the study of data-dependent regret bounds in constrained MAB settings. These bounds depend on the sequence of losses that characterize the problem instance. Thus, they can be much smaller than classical $\widetilde{\mathcal{O}}(\sqrt{T})$ regret bounds, while being equivalent to them in the worst case. Despite this, data-dependent regret bounds have been completely overlooked in constrained MAB settings. The goal of this paper is to answer the following question: Can data-dependent regret bounds be derived in the presence of constraints? We answer this question affirmatively in constrained MABs with adversarial losses and stochastic constraints. Specifically, our main focus is on the most challenging and natural settings with hard constraints, where the learner must ensure that the constraints are always satisfied with high probability. We design an algorithm with a regret bound consisting of two data-dependent terms. The first term captures the difficulty of satisfying the constraints, while the second one encodes the complexity of learning independently of the presence of constraints. We also prove a lower bound showing that these two terms are not artifacts of our specific approach and analysis, but rather the fundamental components that inherently characterize the complexities of the problem. Finally, in designing our algorithm, we also derive some novel results in the related (and easier) soft constraints settings, which may be of independent interest.

Figures

Figures reproduced from arXiv: 2505.20010 by the authors.

**Figure 1.** A graphical representation of the update performed by Algorithm 2. For the sake of exposition, we omit the constraint [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 18 canonical work pages

[1]

(5) 13 ARXIV PREPRINT - JULY 12, 2025 The result above holds since eSt is a polytope (thus, convex) for any t ∈ [T ]

Then, we apply standard OMD with log-barrier results (see [Agarwal et al., 2017]) to obtain: TX t=1 bℓt ⊤ (xt − u) ≤ TX t=1 (Dψt (u, xt) − Dψt (u, xt+1)) + TX t=1 KX a=1 ηt,ax2 t (a) bℓt 2 (a). (5) 13 ARXIV PREPRINT - JULY 12, 2025 The result above holds since eSt is a polytope (thus, convex) for any t ∈ [T ]. As eSt is included in ∆K, then the intersecti...

work page 2017
[2]

Notice that, xt+1 is computed pessimistically

Finally, in Figure 1(c), we provide how the convex combination is performed. Notice that, xt+1 is computed pessimistically. Indeed, due to the high uncertainty in the constraints estimation, xt+1 is an interior point of the safe space. B Related Works Data-Dependent Regret Bounds Over the last two decades, in the literature on (unconstrained) adversarial ...

work page 2006
[3]

With probability at least 1 − δ, SOLB guarantees that g⊤ i xt ≤ αi holds for every action a ∈ [K], constraint i ∈ [m], and round t ∈ [T ]

Let δ ∈ (0, 1). With probability at least 1 − δ, SOLB guarantees that g⊤ i xt ≤ αi holds for every action a ∈ [K], constraint i ∈ [m], and round t ∈ [T ]. Proof. To prove the result, we consider separately the case in which γt = 0 and γt ∈ (0, 1). Notice that, when γt = 1, the constraints are trivially satisfied by definition of the strictly feasible solu...

work page 2025
[4]

Let δ ∈ (0, 1), ρ ≥ 12K T , and η = min n ρ 40H ln T ln(H/δ) , p K/PT t=1 ℓ⊤ t x∗ ln(1/δ) o , where H := ln (⌈ln(T )⌉⌈3 ln(T )⌉/δ). Then, SOLB suffers a cumulative regret bounded as: RT (ℓ1:T ) ≤ eO K ln (1/δ) ρ vuut TX t=1 ℓ⊤ t (x⋄ − x∗) 2 | {z } (A) Safety Complexity + 1 ρ vuutK TX t=1 ℓ⊤ t x∗ ln 1 δ | {z } (B) Bandit Complexity ! , (3) where eO hides u...

work page 2025
[5]

In the following, we define h(y) = y − 1 − ln y. Thus we bound the first two term of Equation (5) as follows: TX t=1 (Dψt (u, xt) − Dψt (u, xt+1)) ≤ Dψ1 (u, x1) + T −1X t=1 Dψt+1 (u, xt+1) − Dψt (u, xt+1) (6) = 1 η KX a=1 h u(a) x1(a) + KX a=1 T −1X t=1 1 ηt+1,a − 1 ηt,a h u(a) xt+1(a) , where Inequality (6) holds since the Bregman is always greater or eq...

work page 2025
[6]

Hao Yu, Michael Neely, and Xiaohan Wei

doi: 10.1145/3179415. Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30,

doi:10.1145/3179415
[7]

• In Appendix B, we provide the complete discussion on related works

11 ARXIV PREPRINT - JULY 12, 2025 Appendix The Appendix is structured as follows: • In Appendix A, we provide a graphical representation of Algorithm 2’s update. • In Appendix B, we provide the complete discussion on related works. • In Appendix C, we provide the omitted analysis for the soft constraints setting. • In Appendix D, we provide the omitted an...

work page 2025
[11]

Et h bℓt i − bℓt ⊤ xt 2# = Et

Furthermore, we bound the second moment as: Et " Et h bℓt i − bℓt ⊤ xt 2# = Et " ℓt − bℓt ⊤ xt 2# ≤ Et bℓ ⊤ t xt 2 ≤ Et h bℓ ⊤ t xt i = ℓ⊤ t xt. Thus we can apply the Freedman inequality to attain, with probability at least 1 − δ: TX t=1 (ℓt − bℓt)⊤xt = O   vuut TX t=1 ℓ⊤ t xt ln 1 δ + ln 1 δ   . Bound on the third term To bound the third term, we aga...

work page 2025

Show all 21 references

[12]

Then, with probability at least 1 − 2δ, the COLB algorithm suffers cumulative positive constraint violations VT ≤ O p KT ln (T Km/δ)

Let δ ∈ (0, 1). Then, with probability at least 1 − 2δ, the COLB algorithm suffers cumulative positive constraint violations VT ≤ O p KT ln (T Km/δ) . Proof. First, we underline that the following analysis holds for every constraint i ∈ [m], including the one being violated th...

2025
[13]

and ρ ≥ 12K T . Then, with probability at least 1 − 2δ, SOLB satisfies: R⋄ T (ℓ1:T ) ≤ O   K ρ vuut TX t=1 ℓ⊤ t (x⋄ − x∗) 2 · ln KT m δ + K ρ6 ln KT m δ   , (2) where R⋄ T (ℓ1:T ) := PT t=1 γt−1ℓ⊤ t (x⋄ − x∗). Proof. We first split the round in two setsT1, T2. T1 encompass...

2025
[14]

Thus, we proceed as follows: Et   KX a=1 xt(a) − 1 t(a) max{1, Nt−1(a)} !2  ≤ Et " K KX a=1 xt(a) − 1 t(a) max{1, Nt−1(a)} 2# = K KX a=1 Et (xt(a) − 1 t(a))2 max{1, N2 t−1(a)} = K KX a=1 xt(a)(1 − xt(a)) max{1, N2 t−1(a)} ≤ K KX a=1 xt(a) max{1, Nt−1(a)} , and we apply Lem...

2020
[15]

and η ≤ ρ 40H ln T ln(H/δ), where H := ln (⌈ln(T )⌉⌈3 ln(T )⌉/δ). Then, with probability at least 1 − 2δ, SOLB satisfies: eRT (ℓ1:T ) ≤ O K η + η ρ TX t=1 ℓ⊤ t xt + Kη ρ ln 1 δ + vuut TX t=1 ℓ⊤ t xt ln 1 δ + η ρ TX t=1 ℓ⊤ t x∗ ln 1 δ ! , where eRT (ℓ1:T ) = PT t=1(1 − γt−1)ℓ⊤ ...

2025
[16]

(1 − γt−1) Et h bℓt i − bℓt ⊤ ext 2# = Et

Furthermore, we bound the second moment as: Et " (1 − γt−1) Et h bℓt i − bℓt ⊤ ext 2# = Et " (1 − γt−1) ℓt − bℓt ⊤ ext 2# ≤ Et (1 − γt−1)bℓ ⊤ t ext 2 ≤ Et bℓ ⊤ t xt 2 22 ARXIV PREPRINT - JULY 12, 2025 ≤ Et h bℓ ⊤ t xt i = ℓ⊤ t xt. Thus we can apply the Freedman inequality to a...

2025
[19]

Let K ≥ 2, T ≥ max n 2, (11 + lnT ) 8 3 2o , and ω ∈ 1 T 11 2 + ln T , 1 2 . Then for every randomized algorithm, we have supℓ1:T ∈Bω,∆,T E[RT (ℓ1:T )] ≥ Ω ∆ ρ √ T + √ ωT , where the expectation is taken with respect to the internal randomization of the algorithm. Proof. We sp...

2025
[20]

TX t=1 xt(ai) # ≤ Eν 4

is the only strictly safe strategy. We start by considering ν1: in order to be safe with high probability, for a given confidence level δ ∈ (0, 1), any algorithm must satisfy: Pν 1 ∀t ∈ [T ] : xt(a3) ≥ ϵ ϵ + ρ ≥ 1 − δ, where xt is the strategy of the algorithm at timet, and Pν...

2016
[21]

Suppose by contradiction that, for every ℓ1:T s.t. Equation (16) holds, then Eν 2 [RT (ℓ1:T )1 Eq.(16)] < 9 2048 √ T ω+ 1 48ρ ∆ √ T , Then, by setting δ′ = 1 228T , we have: Eν 2 [RT (ℓ1:T )] = Eν 2 [RT (ℓ1:T )1 Eq.(16)] + Eν 2 [RT (ℓ1:T )(1 − 1 Eq.(16))] < 9 2048 √ T ω+ 1 48ρ...
[2002]

Provably efficient model-free algorithm for mdps with peak constraints

Qinbo Bai, Vaneet Aggarwal, and Ather Gattami. Provably efficient model-free algorithm for mdps with peak constraints. arXiv preprint arXiv:2003.05555,

2003 arXiv
[2006]

The nonstochastic multiarmed bandit problem

9 ARXIV PREPRINT - JULY 12, 2025 Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48–77,

2025
[2018]

Hannan consistency in on-line learning in case of unbounded losses under partial monitoring

Chamy Allenberg, Peter Auer, László Györfi, and György Ottucsák. Hannan consistency in on-line learning in case of unbounded losses under partial monitoring. In Algorithmic Learning Theory: 17th International Conference, ALT 2006, Barcelona, Spain, October 7-10,

2006
[2020]

Learning adversarial mdps with stochastic hard constraints

Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning adversarial mdps with stochastic hard constraints. arXiv preprint arXiv:2403.03672, 2024a. Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Optimal str...

arXiv
[2024]

Explore no more: Improved high-probability regret bounds for non-stochastic bandits

10 ARXIV PREPRINT - JULY 12, 2025 Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015a. Gergely Neu. First-order regret bounds for combinatorial semi-bandits. In Conferenc...

2025

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

(5) 13 ARXIV PREPRINT - JULY 12, 2025 The result above holds since eSt is a polytope (thus, convex) for any t ∈ [T ]

Then, we apply standard OMD with log-barrier results (see [Agarwal et al., 2017]) to obtain: TX t=1 bℓt ⊤ (xt − u) ≤ TX t=1 (Dψt (u, xt) − Dψt (u, xt+1)) + TX t=1 KX a=1 ηt,ax2 t (a) bℓt 2 (a). (5) 13 ARXIV PREPRINT - JULY 12, 2025 The result above holds since eSt is a polytope (thus, convex) for any t ∈ [T ]. As eSt is included in ∆K, then the intersecti...

work page 2017

[2] [2]

Notice that, xt+1 is computed pessimistically

Finally, in Figure 1(c), we provide how the convex combination is performed. Notice that, xt+1 is computed pessimistically. Indeed, due to the high uncertainty in the constraints estimation, xt+1 is an interior point of the safe space. B Related Works Data-Dependent Regret Bounds Over the last two decades, in the literature on (unconstrained) adversarial ...

work page 2006

[3] [3]

With probability at least 1 − δ, SOLB guarantees that g⊤ i xt ≤ αi holds for every action a ∈ [K], constraint i ∈ [m], and round t ∈ [T ]

Let δ ∈ (0, 1). With probability at least 1 − δ, SOLB guarantees that g⊤ i xt ≤ αi holds for every action a ∈ [K], constraint i ∈ [m], and round t ∈ [T ]. Proof. To prove the result, we consider separately the case in which γt = 0 and γt ∈ (0, 1). Notice that, when γt = 1, the constraints are trivially satisfied by definition of the strictly feasible solu...

work page 2025

[4] [4]

Let δ ∈ (0, 1), ρ ≥ 12K T , and η = min n ρ 40H ln T ln(H/δ) , p K/PT t=1 ℓ⊤ t x∗ ln(1/δ) o , where H := ln (⌈ln(T )⌉⌈3 ln(T )⌉/δ). Then, SOLB suffers a cumulative regret bounded as: RT (ℓ1:T ) ≤ eO K ln (1/δ) ρ vuut TX t=1 ℓ⊤ t (x⋄ − x∗) 2 | {z } (A) Safety Complexity + 1 ρ vuutK TX t=1 ℓ⊤ t x∗ ln 1 δ | {z } (B) Bandit Complexity ! , (3) where eO hides u...

work page 2025

[5] [5]

In the following, we define h(y) = y − 1 − ln y. Thus we bound the first two term of Equation (5) as follows: TX t=1 (Dψt (u, xt) − Dψt (u, xt+1)) ≤ Dψ1 (u, x1) + T −1X t=1 Dψt+1 (u, xt+1) − Dψt (u, xt+1) (6) = 1 η KX a=1 h u(a) x1(a) + KX a=1 T −1X t=1 1 ηt+1,a − 1 ηt,a h u(a) xt+1(a) , where Inequality (6) holds since the Bregman is always greater or eq...

work page 2025

[6] [6]

Hao Yu, Michael Neely, and Xiaohan Wei

doi: 10.1145/3179415. Hao Yu, Michael Neely, and Xiaohan Wei. Online convex optimization with stochastic constraints. Advances in Neural Information Processing Systems, 30,

doi:10.1145/3179415

[7] [7]

• In Appendix B, we provide the complete discussion on related works

11 ARXIV PREPRINT - JULY 12, 2025 Appendix The Appendix is structured as follows: • In Appendix A, we provide a graphical representation of Algorithm 2’s update. • In Appendix B, we provide the complete discussion on related works. • In Appendix C, we provide the omitted analysis for the soft constraints setting. • In Appendix D, we provide the omitted an...

work page 2025

[8] [11]

Et h bℓt i − bℓt ⊤ xt 2# = Et

Furthermore, we bound the second moment as: Et " Et h bℓt i − bℓt ⊤ xt 2# = Et " ℓt − bℓt ⊤ xt 2# ≤ Et bℓ ⊤ t xt 2 ≤ Et h bℓ ⊤ t xt i = ℓ⊤ t xt. Thus we can apply the Freedman inequality to attain, with probability at least 1 − δ: TX t=1 (ℓt − bℓt)⊤xt = O   vuut TX t=1 ℓ⊤ t xt ln 1 δ + ln 1 δ   . Bound on the third term To bound the third term, we aga...

work page 2025