- 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
-
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.
-
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.
-
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.
-
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
- Can the authors give a concrete non-product application where the general assumptions hold and yield informative regret bounds?
- Under identical feedback and sampling constraints, what improvement remains over appropriate structured or linear-bandit methods beyond the restricted certificate comparison?