acceptodds
Under review as a conference paper at ICLR 2027

Prior-Free Adaptation in Improving Bandits: Free without Noise, Costly under Noise

Abstract

Improving bandits model decision problems in which rewards increase with repeated investment in an arm while exhibiting diminishing returns. Existing guarantees rely on prior knowledge of problem-dependent quantities such as reward scale, a lower-envelope parameter, or the horizon. We ask whether such prior information is fundamentally necessary. Our first result shows that unknown scale is essentially free. We remove the logarithmic overhead in previous scale-oblivious guarantees and obtain the optimal all-horizon competitive ratio without knowing the reward scale. More generally, in the noiseless setting, a single anytime algorithm simultaneously adapts to unknown scale, unknown lower-envelope parameter , and unknown horizon, achieving the optimal ratio for every whose lower-envelope condition holds for an optimal arm. Thus, the price of prior-free adaptation is constant. We then show that this picture changes under bounded multiplicative noise, with observations fixed by an oblivious adversary. Unknown scale alone remains essentially free, but simultaneously adapting to both scale and incurs a growing cost. For any fixed , we establish a structural asymptotic lower bound of order on the uniform price of adaptation, and give a matching algorithm achieving . The uniform price is the minimax loss relative to over , instances, noise tables, and horizons , among algorithms knowing neither scale nor . Knowing either the scale or alone restores a constant price. Together, these results reveal a sharp separation between noiseless and noisy improving bandits. Prior-free adaptation is possible at constant cost without noise, while multiplicative noise creates a growing multiscale adaptation cost when scale and envelope information are unknown.

Primary area:
learning theory
Keywords:
Improving multi-armed bandits, Competitive analysis, Prior-free algorithms, Anytime algorithms, Multiplicative noise

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_EBs5OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies whether an online learning algorithm can achieve the optimal competitive ratio in improving multi-armed bandits without prior knowledge of problem-dependent parameters, and how the answer changes when rewards are noisy. Authors show that those priors are unnecessary up to constant factors in the noiseless setting, but bounded adversarial multiplicative noise creates a fundamental difficulty when both reward scale and curve-shape information are unknown.

Critical strengths

Frankly, I cannot verify the correctness and soundness of this paper due to poor presentation (see weakness). Suppose that all results are correct, and then the contributions are as follows:

  • Authors propose an algorithm that achieves O(k)O(\sqrt{k}) competitive ratio without prior knowledge of the reward scale, removing O(log⁡k)O(\log k) term in prior work. They also establish the optimal all-horizon competitive ratio of Θ(k+k/T)\Theta(\sqrt{k}+k/T).

  • Authors develop an algorithm that achieves the optimal competitive ratio O(kβ/(1+β)+k/T)O(k^{\beta/(1+\beta)}+k/T) simultaneously for all β∈(0,1]\beta \in (0,1] without knowing the reward scale, lower-envelope exponent, or horizon.

  • Under bounded adversarial multiplicative noise, the authors show that simultaneously adapting to an unknown reward scale and lower-envelope exponent will incur an unavoidable additional factor.

Critical weaknesses

The major weakness of this paper is its presentation. Even if I spend much time reading, it's hard for me to parse the paper. There are too many coherence and presentation issues. I just list some as examples (I do not include all issues, but I hope the authors themselves can at least go through the paper once).

  1. In the 1st paragraph of introduction, it is totally unclear the meaning of uniform when you refer to ``A uniform guarantee is different''
  2. In the 1st paragraph of introduction, there is no definition of ALGTALG_T.
  3. In the 2nd paragraph of introduction, there is no context for me to understand ``an absolute threshold''.
  4. In the 2nd paragraph of introduction, no definition for f∗f^* and βI\beta_I (though there is definition for β\beta, but what is subscript II for?)
  5. In the caption of figure 1, what's the meaning of uniform price? Uniform price appears multiple times without a clear definition.
  6. In contribution paragraphs, it is unclear to readers what are proposed algorithms unless they carefully check in algorithm section. First, in the first bullet, it starts with ``Probe-and-commit''
  7. In the third bullet of contribution paragraphs, what's the two increment-based repairs when you referring ``Random-marginal probing and two increment-based repairs fail with unbounded ratio''. What's the Nested random-permutation probing? Please at least let readers know which algorithms are proposed by this paper.
  8. More importantly, I try my best to read the first section, but still cannot understand the high-level idea on why the logarithm disappears.

Overall: It's extremely hard to follow this paper, and I cannot verify the soundness and correctness of this paper, even just in a high-level.

Questions for authors

I just hope that the authors can significantly improve the presentation of the paper, which make it easy to follow.

Reviewer_wS6LOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies how much prior information is needed to achieve good cumulative reward in improving bandits, where each arm’s rewards grow with use but have diminishing returns. In the noiseless setting, it gives an anytime algorithm that adapts to the unknown reward scale, growth-envelope exponent, and horizon while attaining the optimal competitive-ratio order. With bounded multiplicative noise fixed by an oblivious adversary, unknown scale alone remains inexpensive, but jointly lacking scale and the growth-envelope exponent has a growing adaptation cost: the paper proves matching upper and lower bounds. Knowing either parameter restores a constant adaptation price.

Critical strengths

A strength is the paper’s systematic treatment of which information helps and when: it distinguishes guarantees tuned to a particular β\beta from a single policy that works across all β\beta, and it supplies matching bounds for several information settings, including unknown horizons.

Critical weaknesses

I'd say the critical weakness is the exposition. No serious human author would write a paper without properly introducing the related works... Also, the contributions are not properly contextualized in the literature.

At this age, writing human things for human readers is important. AI can produce technical results at large scale...

Questions for authors

N/A.

Reviewer_woHFOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies the improving bandits problem and provides optimal results (measured using competitive ratio) when instance parameters are not known.

Critical strengths

The paper tries to develop optimal algorithms for improving bandits when the problem parameters are not known. Many algorithms in the bandit literature unfortunately require knowing such parameters, so efforts to reduce dependency on this knowledge is appreciated.

Critical weaknesses

The paper is impossible to read since it uses language that is completely non-traditional in the bandit community. This starts right in the introduction section - without giving any proper motivation or explanation of the problem statement the paper starts using jargon which makes it very difficult to read. For example - the very first paragraph uses terms like discretely concave, delayed-reveal etc. and starts highlighting lower bounds from prior work without defining the parameters involved (they mention Ω(LT)\Omega(LT) lower bound without mentioning what LL or TT are) makes it difficult to make any sense of the work. This continues throughout the paper. There is also very little motivation provided for the model studied in the paper either directly or by citing prior work. I have struggled to understand the technical part of the work even after giving it sufficient time and believe the paper needs significant rewriting. In the current form of the paper my decision would be to reject it. I hope the authors carefully re-write making it helpful for reviewers to appreciate the contribution.

Questions for authors

NA

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.