acceptodds
Withdrawn from ICLR 2027

Learning Unknown Oscillators from Bandit Feedback

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We study semi-bandits driven by unknown oscillators. Each round, a learner selects two of four reward channels and observes their individual rewards. Frequency errors change future reward rankings and the resulting measurements. We show when committing to one fitted oscillator lets its greedy choices expose prediction errors. Our controller bounds reward loss (regret) over a continuous confidence set and holds the longest block within budget. An online regression policy gathers observations when the check fails. Regret grows at a square-root rate, up to logarithmic factors, across all frequencies and extends to two competing oscillators. On 96 fresh synthetic instances, checked commitment uses 49 fits instead of 1,023, with 1.5% higher mean regret than fitting every round. Matched isolated timings give a 4.69-fold speedup. The confidence sets also certify trajectory regret.

Primary area:
learning theory
Keywords:
bandits, frequency estimation, online learning, regret bounds, oscillators, greedy algorithms, semi-bandits

Reviews

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

This paper studies a bandit problem where the rewards of four arms are driven by a hidden signal that rotates in a circle at an unknown constant speed (an oscillator). Two arms measure the horizontal position of the rotating signal and two measure its vertical position, and the learner chooses two arms each round. Choosing both arms of the higher direction maximizes immediate reward, but leaves the other direction unobserved. The authors observe that if a learner switches between different plausible explanations from round to round, it can avoid ever measuring the direction that would expose its model as wrong. By contrast, committing to a single fitted oscillator for a block of rounds causes its greedy choices to rotate and eventually test both directions. Building on this idea, the paper proposes a controller that fits an oscillator, checks over a confidence set how much regret holding that model could incur, and falls back to an online learner when the check fails.

Critical strengths
  • The basic setup in Sections 1 and 3 is an interesting toy model for studying how greedy reward-maximizing choices interact with system identification in a time-varying environment.
  • The noiseless counterexample in Section 3 (Proposition 1) and the geometric result in Section 4 (Theorem 1) give a nice intuition for why sticking to a single model for a block of rounds can expose reflection aliases that a policy switching between models might miss.
Critical weaknesses
  • While the setup is understandably a simplified toy problem, the introduction does very little to connect it to broader real-world settings (offering only a single brief sentence on recurring network demand) or to standard state-space formulations. Mathematically, the model is just a parameterization of an undamped 2D linear dynamical system (xt+1=Axtx_{t+1} = A x_t with a rotation matrix A=R(ω)A = R(\omega) and action-dependent coordinate observations). Framing and motivating the problem in terms of standard linear dynamical systems and real applications where greedy exploitation conflicts with state or system observability would make the contribution much clearer.

  • The writing and presentation make the paper very hard to follow. While the initial setup in Section 3 is mostly followable, from Section 4 onward (Sections 4 to 8) the prose consists almost entirely of short, disconnected declarative sentences without logical transitions, reading more like compressed notes than a coherent explanation (for example, the paragraphs following Theorems 1 and 2, or the sudden appearance of Proposition 2 at the end of Section 6 with no transition). In addition, terms and algorithmic components are dropped into the text with little introduction or context, such as the sudden reference to "our oscillator posterior comparator" at the end of Section 2 (five pages before the experiments are introduced), or Algorithm 1 saying to "run SquareCB" and "update its regressors" without minimally introducing SquareCB or what those regressors are.

  • The 9-page main text is not self-contained and omits the mathematical definitions of core components needed to understand how Algorithm 1 operates. Specifically, Algorithm 1 relies on constructing a confidence set CnC_n and falling back to an online learner when the block check fails, yet neither is properly defined in the main body. Section 7 ("Computing Useful Confidence Bounds") rewrites the empirical squared loss Ln(ν,x)L_n(\nu, x) as a quadratic form, but then only says in prose that priors "supply a sequential exponential loss test" without ever writing down the test or the formula defining the confidence set CnC_n. Similarly, Theorem 2 explicitly refers the reader to "the online learner of Appendix B", with Section 6 offering only two vague sentences about a "two-dimensional linear learner" and "aggregation over a sufficiently fine full-circle cover" instead of defining the learner in the main text.

Questions for authors

N/a

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

This paper studies a four-armed bandit model where the algorithm chooses two arms at each time, and where the reward of each arm is driven by a two-dimensional oscillator. As a result, the four arms form two pairs, and the arms within each pair have identical means at any given time. The paper presents an algorithm and analysis for this setting.

Critical strengths
  1. The focus on oscillation could be of interest. An oscillator has persistent memory, whereas the literature on bandits with memory often assumes finite or decaying memory. If the oscillator setting is not already subsumed by prior work, studying it could be valuable. (This would require a complete rewrite and a more general setting.)
Critical weaknesses
  1. The setting is too simple, and I am not convinced it is not already covered by prior work. Choosing two of four arms is oddly restrictive, and since the arms come in identical pairs, the model reduces to a single two-dimensional oscillator with a single frequency. As I explain in the questions below, this appears to be a special case of linear bandits with latent linear dynamics, which have been studied in recent work. This matters because the setting is too simplistic for the results to be worth assessing on their own, and it is not clear what the paper adds beyond existing work.

  2. The writing is poor. The introduction jumps right into the details of the setting without connecting to motivation, applications, or prior academic work. The contributions section is smooth at the surface level, but it is not clearly laid out, and the contributions are not mapped to the results. This pattern holds throughout the paper, which does not follow the conventions of a research contribution beyond the surface level. This matters because a reader cannot tell what the paper contributes or how it relates to the literature.

Questions for authors

Clarifications:

  1. Can the authors provide additional comparison with Oh et al. (2019)?

  2. Since oscillations can be by linear dynamics, there should be more discussion of the connection to prior work in that setting. In particular, the two cited papers by Gornet, and additionally the recent work by Choi et al., "Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics." How is the present paper not just a special case of these models?

Suggestions:

  1. Writing. The introduction should begin with the broader motivation, applications, and prior academic work before going into the details of the setting. The contributions section should be rewritten so that each contribution is stated clearly and mapped to the corresponding result. More generally, I suggest the authors read the related works more closely and follow their conventions if they want to develop this idea further.

  2. Generalization. Why is the setting restricted to choosing two of four actions, and why do the four arms reduce to identical pairs? It seems odd not to study a higher-dimensional version of this problem, for example linear dynamics with a general transition matrix as above. If the oscillator setting is not already subsumed by prior work, it could be of interest as a proper research project in a more general setting, with the theory and algorithms developed for that case.

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

This paper considers a semi-bandit problem driven by an unknown oscillator. The authors investigate how committing to a fitted oscillator model can help reveal prediction errors through the observations generated by its own decisions, and use this idea to develop a checked commitment framework based on confidence sets. The paper presents theoretical guarantees, trajectory-level regret certificates, and a two-oscillator extension, and evaluates the approach against frequent refitting, sparse refitting.

Critical strengths
  • The core idea is interesting. The observation that committing to a fitted oscillator can generate measurements that reveal its own prediction errors is insightful.
Critical weaknesses
  • The experiments do not clearly demonstrate the benefit of the confidence-checking mechanism itself. In the main experiments, a simpler variant that follows a similar sparse refitting schedule without checking appears to achieve comparable regret at lower computational cost. This suggests that much of the observed speedup may come from reducing the frequency of refitting rather than from the checking procedure itself.
  • The paper is difficult to read. Important concepts and contributions are introduced gradually and often without enough intuition. I found it unnecessarily hard to identify the main message of the paper.
  • The setting is fairly specialized and evaluated only on synthetic data, making it difficult to judge the broader applicability of the approach.
Questions for authors
  • Can the connection between Theorem 1 and the controller be made more explicit?
  • Can the authors provide evidence that isolates the benefit of the checking mechanism from sparse refitting alone?
Reviewer_6LRROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies a structured nonstationary semi-bandit problem, in which rewards follow an oscillator with fixed but unknown frequency and initial state. Thee main result shows when a held candidate model's greedy measurements control the prediction error of the held block as well as the following block (Theorem 1). The paper also proposes a controller that evaluates proposed commitment blocks against a continuous confidence set, and uses SquareCB when the checks fail (Algorithm 1). The method achieves a T\sqrt{T} regret (Theorem 2). They evaluate on synthetic experiments.

Critical strengths

The result in Theorem 1 can be interesting. It shows that a sufficiently long block of a fixed candidate’s greedy measurements controls prediction errors in both coordinates throughout the observed block and an equally long future block. Such a candidate model does not need to already be accurate. The result can potentially go beyond the current setting.

Critical weaknesses

I am mostly concerned about the motivation of the specific formulation. From the start of the paper, it's unclear why this problem is considered. It's only when reading "Information from greedy choices" in the Related work section that I kinda can guess maybe the properties of greedy strategies is what you are interested in. Still, I wonder whether this is the most natural and suitable setting for such investigation. Perhaps, some more background of the motivation should be furthered. In relation to this, I have mainly the three questions listed in the following section. I am open to change my opinion.

You also listed a few references about bandit problems with periodic structures, Oh et al. (2019) and Chen et al. (2025), in particular. However, I find the comparison and discussion rather limited.

Questions for authors
  1. You seem to introduce the setting of "having two arms for each coordinate, and allowing the learner to select two arms and observe their individual rewards each round" in order to study the tradeoff between getting higher rewards and getting information about the periodic structure. This makes me wonder whether the setting is mainly motivated by technical considerations. Do you have a natural motivating example where these assumptions arise together and make this tradeoff particularly interesting?

  2. Your Theorem 1 shows that commitment (or greedy) strategy provides information that can control the held block and the next block with the same length, which is pretty interesting. Given this, I would expect to see some further derivations or implications based on the theorem. It is possible that I missed something, but it does not seem to be used to obtain the subsequent results, particularly Theorem 2. Also, it does not seem to tell us when or how Dn/nD_n/n becomes small for the models used by Algorithm 1. Could you explain the connection, and whether it can lead to, e.g., fewer model refits?

  3. I am also wondering about the construction of the problem setting when trying to understand Theorem 2. Generally speaking, this is a structured non-stationary bandit problem: the rewards change over time, but they follow fixed, unknown oscillator dynamics. In general variation-budget formulations, a fixed positive variation budget can lead to T2/3T^{2/3}-type minimax dynamic regret. So it is nice to see a O~(T)\widetilde O(\sqrt T) guarantee here, which I guess mainly comes from the oscillator structure. Now, I am thinking: if the goal is to obtain this regret rate, could the setting be simpler, without two arms per coordinate and semi-bandit feedback? For example, could we just have two arms corresponding to the horizontal and vertical coordinates, selecting and observing one arm each round? I could be misunderstanding your approach, but my feeling is that a rather direct use of SquareCB could already achieve the same order of regret in this simpler setting. In particular, we could treat time tt as the context and adapt the frequency-indexed online regression construction in Appendix B, and apply SquareCB. So, maybe in relation also to my first two questions, what additional benefits do we get from commitment?

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

Related papers

Discussion (0)

Sign in to comment.