acceptodds
Under review as a conference paper at ICLR 2027

Shared-Observation Chaining for Hierarchical Adversarial Noisy Bandits

18 views

Abstract

We study finite-time regret in adversarial noisy bandits with bounded conditional-mean feedback. Fixed-scale optimizer-cover scalars are not rate-complete: two finite-action classes agree on a nontrivial scale range yet have exponentially different regret. On a product routing model with templates, a known-horizon -time learner uses one route/reward observation to update all active levels and attains expected regret against adaptive nonanticipating environments; an oblivious Bernoulli subclass matches this rate. Even the optimistic fixed-rate one-global-Shannon ExO expression, with arbitrary finite real-valued Borel scores, is . A simultaneous product packing matches the complete active-coordinate finite-horizon profile ; in the information-limited regime this becomes , without a block-allocation depth loss. Under explicit margin, finite-range, matching, quadratic-regime, allocation, saturation, and terminal-control conditions, general optimizer hierarchies admit a conditional chain–packing comparison.

Primary area:
learning theory
Keywords:
adversarial noisy bandits, online learning, minimax regret, hierarchical bandits, partial monitoring, exploration by optimization, sequential chaining, information-theoretic lower bounds

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_ZuSdOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

1. Summary

The paper studies adversarial noisy bandits with a known stochastic routing mechanism. It develops an algorithm that updates multiple coordinates from one route/reward observation, proves matching regret bounds for a product model, and proposes a more general conditional framework for hierarchical problems.

Critical strengths
  • The product-model algorithm is explicit and computationally efficient, with matching upper and lower regret bounds.
Critical weaknesses
  1. Clarity and presentation are major weaknesses. The paper is extremely difficult to follow and is not ready for publication in its current form. Specialized terminology and technical statements are introduced before the problem, motivation, and central ideas are adequately explained. For example, Section 6 states central bounds using complexity measures that are only informally described there. Dense theorem statements, uneven font sizes, and extensive appendices further hinder understanding. These issues require substantial restructuring and rewriting, beyond local editing, to make the formulation, contributions, and arguments accessible and assessable.

  2. The motivation is insufficient. The introduction begins almost immediately with a mathematical construction, without adequately explaining the underlying learning problem or why its restrictions are useful. The flagship result relies on product routing, additive rewards, and geometrically decaying coordinate reliabilities. The relevance of this particular combination needs a clearer justification.

  3. The main comparison has limited scope. Section 5 establishes a separation from a particular fixed-rate global-Shannon certificate. Although this restriction is acknowledged, the paper does not convincingly establish an advantage over suitable structured bandit methods using the same observations.

  4. The broader framework has limited demonstrated applicability. Theorems 7.1–7.2 require numerous conditions whose joint usefulness beyond product examples remains unclear. Moreover, Theorem 8.3 evaluates a fixed-design subproblem; it does not provide a general procedure for selecting the hierarchy and sampling design.

Questions for authors
  1. Can the authors give a concrete non-product application where the general assumptions hold and yield informative regret bounds?
  2. Under identical feedback and sampling constraints, what improvement remains over appropriate structured or linear-bandit methods beyond the restricted certificate comparison?
Reviewer_rbe4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies structured adversarial noisy bandits with known product routing templates, additive reward means, and feedback consisting of the sampled route and one bounded scalar reward. Against the best fixed template, it proves the minimax profile

ΨT(λ,α)=∑j:αj>0λjmin⁡{αjT,T},\Psi_T(\lambda,\alpha)=\sum_{j:\alpha_j>0}\lambda_j\min\{\alpha_jT,\sqrt T\},

with an adaptive upper bound and an oblivious Bernoulli lower bound. Geometric execution biases yield a canonical Θ(√T) rate with O(D) work despite 2^D templates. The paper separates this rate from a specified fixed-rate, one-global-Shannon ExO expression. Shared-design chain upper certificates, compatible sequential packing lower bounds, conditional comparisons, affine estimation geometry and a fixed-design quadratic SOCP extend the discussion.

Critical strengths
  1. A precise matching result for the product family. The finite-horizon profile accounts for inactive coordinates, small amplitudes and heterogeneous execution biases. The upper bound addresses adaptive conditional-mean feedback and its random hindsight comparator; the lower construction uses one legal comparator optimal across all coordinates. The exact family-specific characterization deserves credit even if its ingredients have precedents.
  2. A carefully delimited certificate obstruction. The global-Shannon result allows arbitrary finite Borel scores and is explicitly restricted to the specified fixed-rate expression. It is not presented as a lower bound on all flat algorithms or all ExO/DEC methods. Common-design and comparator-compatibility requirements are also made explicit in the general framework.
Critical weaknesses
  1. The methodological increment in the flagship upper bound needs clearer separation from standard tools. For the legal product law, the centered score

    \frac{A_{t,j}-\lambda_jm_{t,j}}{1-\lambda_j^2m_{t,j}^2}$$ is unbiased for `α_jλ_jθ_{t,j}/4`, with second moment at most `V_j=λ_j²/[4(1−λ_j²)]`. Coordinatewise projected gradient ascent from zero, with step `1/√(TV_j)`, gives an expected bound `2√(TV_j)` after the adaptive-hindsight correction. The same learner has the pathwise conditional-mean regret cap `R_j≤α_jλ_jT/2`. Taking the smaller bound recovers the full profile in rate for `λ_j≤1/2`; separate freezing is unnecessary for this purpose, although freezing gives a better small-amplitude constant. The adaptive-comparator correction has a precedent in [Flaxman, Kalai and McMahan (2005), Lemma 3.2](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/2005-Online_Convex_Optimization_in_the_Bandit_Setting.pdf). This is a derivation for the submitted model, not a claim that earlier work states its exact theorem. It weakens the case for a new upper-bound method, without disposing of the matching profile or certificate separation.
  2. The broader modeling and general-framework payoff remains insufficiently demonstrated. Known policies, sampled-outcome identity and scalar loss are already part of Eldowa et al.'s mediator-feedback protocol (JMLR 2024). The product result adds specific structure and an adaptive-hindsight guarantee; the observation mechanism alone is not new. Its additive means, known product channel and summable canonical biases make it a special family. Meanwhile, common-design, gluing, matching, range, horizon, saturation and terminal conditions do substantial work in the general comparison. The canonical routing family should also be distinguished from the exact coherent-chain example in G.8/K.7. A quantitatively favorable nonproduct instantiation would clarify what the larger framework achieves beyond the explicit family. The use of established ingredients is not itself a defect; the concern is the additional consequence established by their combination.

Questions for authors
  1. Does the centered-score projected-gradient argument, including the same-learner cap, recover the complete product profile under your full adaptive protocol? Which specific theorem or insight provides the principal advance beyond this reduction and weighted transcript testing? Please distinguish an exact new family-specific result from a new general method.
  2. Which example satisfies the full common-design, switching, gluing, matching, saturation and terminal conditions with favorable constants and horizon dependence? Which conclusions apply to the canonical product family, and which to the separate G.8/K.7 coherent-chain example? Please compare its resulting rate with existing mediator-feedback methods.
  3. Can you correct or clarify the following appendix issues? H.40–H.42 should state the Pinsker and Bretagnolle–Huber lower bounds separately; the displayed chain does not hold. Lemma I.4 needs g⁰∈G_ρ to assert nonemptiness. For G.2, Q={δ_1,δ_2}, q_0=δ_1, and G={(0,1)} give infimum −1. For K.14, m=2,T=3 gives J_T=2, contrary to the imported T≥2J_T. For P.6, please specify whether approximation is relative to the quadratic certificate or the exact joint saddle optimum.
  4. Can you provide the supplementary scripts promised on page 10, lines 500–502, and commands for their identity, constant, routing, packing and SOCP checks? No script archive was visible on the authenticated submission or revision pages inspected for this review.
Reviewer_55Z7OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies adversarial noisy bandits with hierarchical policy structures. It establishes matching regret bounds for a product routing model, demonstrates limitations of certain optimizer-based quantities and a fixed-rate global-Shannon ExO expression, and develops a general hierarchical comparison framework. However, the paper is extremely difficult to follow, with excessive notation, terminology, and numerous technical results whose connections and significance are not clearly explained.

Critical strengths
  • The paper establishes matching Θ(T)\Theta(\sqrt{T}) regret bounds for a product routing model with 2D2^D templates and provides an algorithm with O(D)O(D) time and memory complexity per round.
Critical weaknesses
  • The presentation is extremely difficult to follow. Even the abstract and Introduction fail to clearly explain the central research problem, motivation, and contributions.
  • The paper introduces excessive notation, specialized terminology, and numerous theorem statements without sufficient intuition.
  • The main algorithmic contribution appears to rely heavily on standard bandit techniques, and its novelty is unclear. The paper does not clearly explain its technical novelty compared with existing methods.
Questions for authors
  • Could the authors clearly explain the motivation for this work and summarize its main contributions?
  • What is the main technical novelty compared with existing adversarial linear bandit algorithms?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.