Triple-Optimistic Learning for Stochastic Contextual Bandits with General Constraints

We appreciate the reviewer's comments and want to address your major concerns below.

• Table reference (Guo & Liu, 2024). We adopt a row-wise split in referencing their work to properly represent their work, as their unified algorithm delivers distinct theoretical guarantees across two regimes: (i) a Slater-free setting yielding $\tilde{O}(T^{\frac{3}{4}})$ bounds for both regret and constraint violation, and (ii) a Slater-satisfied regime achieving sharper $\tilde{O}(\sqrt{T}/\delta^2)$ guarantees.

• The Slater's condition. The Slater condition assumes the existence of a strict feasible solution and is a standard assumption in constrained optimization. While our analysis does not explicitly rely on this condition (its elimination constitutes a key theoretical contribution), we acknowledge the need to formally define it and have included this in our revision.

• Clarification on $\tilde{O}$. The notation $\tilde{O}$ suppresses logarithmic factors, which is consistent with the state-of-the-art works. We will explicitly define it in our revision.

• Experimental setup. Our experiments replicate the methodology in (Guo & Liu (2024)), where contexts are randomly sampled from the MSLR dataset to simulate customer arrivals. We have included a more detailed description in our revision. We have conducted additional experiments to verify our results in non-contextual bandits with stochastic and adversarial constraints. Optimistic$^3$ outperforms all baseline algorithms in both settings, which aligns with our theoretical guarantees. Complete implementation details and supporting figures are available at https://anonymous.4open.science/r/Test-25FA/additional_exp.pdf.

We hope our responses have clarified the reviewer's concerns and that the reviewer can re-evaluate our work. Please feel free to share any additional feedback, and we will address it thoroughly.

We very appreciate the reviewer for the constructive comments and want to address your major concerns below.

• Online regression oracle. The online regression oracle assumption is standard in contextual bandits (Foster et al., 2018; Slivkins et al., 2023; Han et al., 2023; Guo & Liu, 2024; Chzhen et al., 2024; Anonymous, 2025). This assumption extends the UCB/LCB (upper/lower confidence bound) paradigm to handle diverse environmental settings. The LinearUCB algorithm serves as a fundamental example that inherently satisfies this assumption. For broader applications, [R1] presents an efficient binary search method for UCB/LCB construction.

• The usage of UCB/LCB. Both UCB and LCB enhance algorithmic exploration in online learning but serve distinct roles: UCB optimistically guides exploration toward actions with lower estimated rewards but higher uncertainty, prioritizing under-explored regions of the reward space. LCB encourages the exploration of actions that appear marginally unsafe under current estimates (i.e., with higher predicted costs) but may still satisfy constraints upon further investigation. By assigning LCB estimators to cost function, the algorithm temporarily treats these actions as ``safe," enabling exploration of uncertain constraint regions.

• $Q_t$ and $\mathbb{E}_{x}$. While $Q_t$ can be interpreted analogously to Lagrange multipliers (or dual variables), its update rule differs fundamentally due to its optimistic design and unbounded property. This design accelerates convergence and enables our key analytical framework to operate without reliance on the Slater condition. The notation $\mathbb{E}_{x}$ denotes expectation only over the context variable (drawn from a known distribution $\mathbb{P}$), not over the entire history. We apologize for any confusion caused by this notation and have clarified it in the revised manuscript.

• Optimistic decision process. The surrogate function in (6) represents the estimated scores over actions. While prior works (e.g., Chzhen et al., 2024; Anonymous, 2025) directly optimize these scores, we introduce an additional regularization term in (7) to stabilize and smooth the update since we introduce the optimistic design to speed up dual updates and encourage exploration.

• The drift term $\Delta_t$. The Lyapunov drift term $\Delta_t$ quantifies the stability of the virtual queue, enabling us to bound cumulative constraint violations through its analysis (see lines 375–381). This term comes from the direct usage of Lemma 5.6 to replace $Q_t \mathbb{E}_x[\langle\pi_t,\check g_t(x)\rangle]$ in line 293.

• Other comments. (i) The cumulative error of reward in line 312 is a typo, and it should be $\tilde{O}(\sqrt{T})$, the proof can be found in line 699. (ii) We will briefly introduce contextual bandits under stage-wise constraints (also termed safe bandits), where algorithms typically assume access to an initial safe region and rely on the iterative construction of safe decision sets. (iii) We sincerely appreciate your suggestions and will incorporate more intuitive explanations and detailed discussions to ensure the methodology and proofs are easy for readers to follow.

We hope that our response addresses the reviewer's concerns and that the reviewer can re-evaluate our work. Please let us know if you have any further comments, and we will try our best to address them.

---------------------------------------------Reference-------------------------------------------------

[R1] Foster, Dylan, et al. Practical contextual bandits with regression oracles. International Conference on Machine Learning (ICML), 2018.

We sincerely thank the reviewer for the positive feedback. We would like to address your questions as follows.

• "Tripe-optimism". The intuition behind our optimistic dual update stems from the Optimistic Online Mirror Descent in [R1], which accelerates convergence through effectively using predictions. Building on its success in min-max optimization [R2], we adapt this paradigm to design a momentum-driven dual update mechanism. Mathematically, our update incorporates a correction term that acts as a momentum term to predict and exploit trends in the reward-cost tradeoff dynamics, thereby accelerating convergence. We will incorporate these discussions in our revision.

• Regret analysis and prior works. The regret in (4) measures the performance gap between the algorithm's policy and the optimal fixed policy in hindsight, where $\mathbb{E}[\langle \pi^* - \pi_t, \mathbf{f}(x_t) \rangle]$ represents the instantaneous regret at step $t$. Classical primal-dual methods (e.g., Slivkins et al., 2023) necessitate manual bounding of the dual variables and further decouple regret and constraint violation guarantees by independently bounding primal and dual regret terms. Recent work (Guo & Liu, 2024) introduced a refined Lyapunov drift framework to eliminate the knowledge requirement of Slater's condition but still require it hold. In contrast, our approach integrates a unified analytical framework via the pushback lemma (Lemma 5.3), enabling simultaneous control of regret and constraint violations. The optimistic design further facilitates bounding $Q_t$ by incorporating a momentum-driven correction term, circumventing the need for the Slater condition entirely. We will include a comprehensive comparative analysis of these methodologies.

• The pushback lemma. Pushback lemma is a fundamental result in online optimization, particularly when working with Bregman divergences (here we specify as KL divergence). This lemma comes from the strong convexity property and guarantees that the optimization process inherently resists deviations from the optimal solution, with the term $\alpha D(\pi||\pi_{opt})$ quantifying the magnitude of this "pushback" effect.
  Here, $h(\cdot)$ denotes the primary objective function; it forms an OMD-style update as in (7) when combined with the regularization term. By specifying $h(\cdot)$ as the surrogate function in (6), the solution $\pi_{opt}$ corresponds directly to the policy $\pi_t$.
  We have included the discussion of these key terms and supplemented it with additional references to enhance clarity and accessibility.

• Comparable performance with LOE2D. Although both Optimistic$^3$ and LOE2D significantly outperform LagrangeCBwLC (which requires knowledge of Slater's condition), there remains a noticeable gap between them, which appears smaller due to plotting averages. Unlike LOE2D, our approach employs an optimistic design for $Q_t$, which accelerates convergence to the optimal reward-cost tradeoff. This design enables a more refined theoretical analysis that cannot be achieved through LOE2D.

Reference

[R1] Rakhlin, Sasha, and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems (NeurIPS), 2013.

[R2] Mokhtari, Aryan, Asuman E. Ozdaglar, and Sarath Pattathil. Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization.

We sincerely appreciate the reviewer’s meticulous review and constructive feedback. The reviewer's concern is correct, where there are big typos in Lemma $5.6$ (and propagated into Lemma $5.7$). We sincerely apologize for the oversight and any confusion caused. Our proof remains valid when these typos are fixed. We are very thankful that the reviewer liked our "optimistic" idea and theoretical results (yes, they are correct). We are also very excited about these results when we realize that "optimistic" design from adversarial online learning can address the long-standing challenges in stochastic bandits. We sincerely invite the reviewer to re-evaluate the paper based on our response.

• Definition of $\mathbb{E}_x$. The expectation $\mathbb{E}_x$ is taken w.r.t. the context variable, as correctly noted by the reviewer. Here, the variable $x$ follows the distribution $\mathbb{P}$, identical to the distribution of $x_t$. We will specify the definition in our revision.

• Typos in Lemma $5.6$ and Lemma $5.7$.
  As the reviewer correctly identified, the typo in Lemma 5.6 involves the cross term:
  $\mathbb{E}_x[\langle \pi_t,\check g_t(x)\rangle]\mathbb{E}_x[\langle \pi_t,\check g_{t-1}(x)\rangle]$
  which is misplaced by $\mathbb{E}_x[\langle \pi_t,\check g_t(x)\rangle\langle \pi_t,\check g_{t-1}(x)\rangle]$. This typo is unfortunately propagated into Lemma 5.7. Therefore, Lemma 5.7 needs to take care of the corrected cross term, and it is indeed correct by fixing the corresponding terms as follows
  \begin{aligned} &\mathbb{E}x [\langle \pi{t-1}, \check{\mathbf{g}}{t-1}(x)\rangle] \mathbb{E}x [\langle \pi{t}, \check{\mathbf{g}}{t}(x)\rangle] \ \geq &\frac{\mathbb{E}x [\langle \pi{t}, \check{\mathbf{g}}{t}(x)\rangle]^2}{2} + \frac{\mathbb{E}x [\langle \pi{t-1}, \check{\mathbf{g}}{t-1}(x)\rangle]^2}{2} \ & - \mathbb{E}x [| \check{\mathbf{g}}{t-1}(x) - \check{\mathbf{g}}{t}(x) |^2] - |\pi_t - \pi{t-1}|_1^2. \end{aligned} where we fixed the typo of $\mathbb{E}_x [\langle \pi_{t}, \check{\mathbf{g}}_{t}(x)\rangle^2]$ in the original version.
  We have attached a complete corrected proof in https://anonymous.4open.science/r/Pr25/. We apologize for the typo again and thank you very much for your time to read the correction.

• The origin of the typo.
  We want to explain that the reason behind the typo is that when we started working on this problem, we indeed tried the ambitious sample-based design, as you suggested. However, this would have issues when establishing Lemma 5.7.
  Specifically, this design would introduce $\|\check{g}_t(x_t) - \check{g}_{t-1}(x_{t-1})\|^2,$ which is extremely challenging to quantify as the difference between two realizations are involved. Then, when we switched to the current "expected" design, we apologize that we had the copy-paste typos.

• Extension to other Bregman divergences. This can be extended to other Bregman divergences, and we will include a discussion in the appendix.

• "Triple-optimism":
  The term $Q_t$ is characterized as "optimistic" due to its conceptual roots in the Optimistic Online Mirror Descent framework in [R1], which leverages predictions to accelerate convergence. Inspired by its application to min-max problems in [R2], we designed an optimistic dual update mechanism, accelerates adaptation through a correction term that incorporates predictive insights, unlike traditional methods that rely solely on current feedback and employ a "pessimistic" exploration to balance trade-offs without leveraging historical trends. We will incorporate these discussions in our revision.

• Our algorithm for BwK in both worlds:
  We introduce BwK in both worlds to demonstrate the versatility and broad applicability of our triple-optimistic framework. We will explicitly describe the problem setting and background to ensure clarity.

• Other typos and careless expression:
  We greatly appreciate your meticulous feedback and have carefully modified all typos in our revision. We have conducted a full manuscript audit to eliminate any residual oversights.

We emphasize that our results are unaffected by the typos. We sincerely apologize for any confusion caused and deeply appreciate the reviewer's invaluable feedback. We hope the reviewer can re-evaluate our work in light of these clarifications.

Reference

[R1] Rakhlin, Sasha, and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems (NeurIPS), 2013.

[R2] Mokhtari, Aryan, Asuman E. Ozdaglar, and Sarath Pattathil. Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization.