Pith. sign in

REVIEW 5 major objections 5 minor 70 references

Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback

T0 review · 5 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Budget-safe online learning reaches the optimal regret rate while keeping constraint violation bounded.

desk verdict Nice problem setup and plausible algorithm, but Lemma 1 proves the wrong index (f_{t-1} vs f_t), leaving the √T regret and zero-violation claims unsupported. read the letter →

arxiv 2412.03983 v2 pith:TZFYSHAV submitted 2024-12-05 math.OC cs.LG

Shanqi Liu , Xin Liu This is my paper · ORCID
classification math.OCcs.LG MSC 90C2568T05
keywords onlineconvexoptimizationlinearbudgetconstraintsbanditfeedbackLyapunovvirtualqueueregretconstraintviolationprimal-dualalgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies online convex optimization where each decision consumes resources through a fixed but unknown linear mapping, and the learner only observes the realized consumption after choosing. The authors propose SELO, a primal-dual algorithm driven by a virtual queue that tracks cumulative budget overuse, and they claim it attains $\widetilde{O}(\sqrt{T})$ regret with $O(1)$ cumulative constraint violation under soft budget constraints, and $\widetilde{O}(\sqrt{T})$ regret under hard budget constraints. The abstract states the stronger conclusion of zero cumulative constraint violation, while the formal theorem proves $O(1)$. These rates match the $\Omega(\sqrt{T})$ lower bound for unconstrained online convex optimization up to logarithmic factors, so the price of unknown constraints and bandit feedback would vanish asymptotically. The practical significance is that a learner with an energy or monetary budget can learn a good policy without a long conservative warm-up phase.

What carries the argument

The machine is a virtual queue $Q_t$ updated by $Q_{t+1}=\max(Q_t+\hat{g}_t(x_t)+\xi\mathbf{1},0)$, where $\hat{g}_t(x)=\bar{A}_t x+\alpha\|x\|_{\Sigma_t^{-1}}-b$ is a pessimistic estimate of the unknown constraint built from regularized least squares and the confidence radius of linear bandits. The pessimistic term plus the extra $\xi$ pacing pushes the algorithm to under-use the budget, and the queue acts as a dual variable so that the decision step minimizes $V\hat{f}_t(x)+\langle Q_t,\hat{g}_t(x)\rangle+\frac{1}{2\eta}\|x-x_{t-1}\|^2$, a strongly convex and smooth problem. The analysis introduces the $\epsilon_t$-tight feasible set $X_{\epsilon_t}=\{x: Ax\le b-\epsilon_t\mathbf{1}\}$ and uses a one-step bound on 'regret plus Lyapunov drift' together with a Foster-Lyapunov multi-step argument to obtain the anytime high-probability queue bound that carries both the regret and violation conclusions.

What would settle it

Run SELO on a one-dimensional instance with $X=[0,1]$, $A_t=1$, and $b=\beta=T^{-1}$, keeping all other assumptions satisfied, and record the cumulative violation over $T$; then $T_0=\log T/\beta=T\log T$ exceeds the horizon, so the exploration phase alone can consume more than the total budget and an $O(1)$ violation bound would fail.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: under convexity, boundedness, and Slater's condition, SELO with parameter choices $V=\sqrt{T}$, $\eta=1/T$, $\xi=\log^2 T/\sqrt{T}$, and exploration length $T_0=\log T/\beta$ guarantees $R(T)=\widetilde{O}(\sqrt{T})$ and $V(T)=O(1)$ when the budget constraint is soft, and $R(T)=\widetilde{O}(\sqrt{T})$ when the budget is hard and violations are not allowed. The proof route is to show the virtual queue is bounded with high probability at every round via a multi-step Lyapunov drift argument, then translate the bounded queue into both the violation bound and the regret loss from early stopping under the hard budget. The paper presents SELO as improving on anytime-safe projection methods, which it claims incur $\widetilde{O}(T^{2/3})$ regret.

Load-bearing premise

The learner must know the Slater constant $\beta$ in advance, because the exploration phase lasts $\log T/\beta$; if $\beta$ is unknown or very small, the safety and regret guarantees are not delivered.

Editorial extensions

If this is right

  • SELO achieves $\widetilde{O}(\sqrt{T})$ regret with $O(1)$ cumulative violation, so a learner can satisfy a long-run budget without paying an extra $\sqrt{T}$ penalty in safety, closing the gap to the unconstrained lower bound.
  • Under hard budgets the same algorithm keeps regret at $\widetilde{O}(\sqrt{T})$, so an energy- or money-limited system can stop when the budget is exhausted without losing more than the asymptotically optimal amount of objective value.
  • Because the primal update is strongly convex and smooth, each round costs about the same as an unconstrained gradient step, removing the projection bottleneck of anytime-safe methods.
  • The regret/violation trade-off parameter $\xi=\log^2 T/\sqrt{T}$ absorbs the optimistic estimation error, indicating that the unknown-constraint estimation cost only shows up in logarithmic factors.
  • The paper notes the same construction works when only the loss value, not its gradient, is observed, by swapping in two-point or one-point gradient estimators.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If Theorem 1 is right, the virtual-queue-plus-pessimistic-estimator pattern is a template for other partial-feedback resource problems: estimation error is converted into an additive safety margin rather than into a separate feasibility phase, so the algorithm avoids the conservative warm-up of projection-based safe learning.
  • The zero-violation phrasing in the abstract is stronger than the proved $O(1)$ violation; a practitioner should read the guarantee as 'violation bounded by a constant independent of $T$' and check the constant's dependence on problem parameters such as $D$, $F$, and $\beta$.
  • Because the exploration length $T_0=\log T/\beta$ depends on the Slater constant, an extension to unknown $\beta$ would need adaptive exploration or a doubling schedule; the paper's guarantee does not cover that case.
  • In applications where budgets are quotas, such as fairness or carbon caps, the $O(1)$ violation bound would translate into asymptotically perfect quota satisfaction, making SELO a candidate for online fair allocation with unknown resource costs.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper studies online convex optimization with linear budget constraints in a partial-feedback model: after choosing x_t, the learner observes the gradient/value of the loss at x_t and the consumption A_t x_t, where the constraint matrices A_t are i.i.d. with unknown mean A. The proposed SELO algorithm first explores for T0 rounds, then at each round minimizes a strongly convex surrogate consisting of an estimated linearized loss, a pessimistic estimated consumption term multiplied by a virtual queue, and a proximal penalty; the virtual queue accumulates pessimistic estimated violations plus a slack xi. The main claims are O~(sqrt(T)) regret with O(1) (and in the abstract, zero) cumulative violation under soft budgets, and O~(sqrt(T)) regret under hard budgets, under convex Lipschitz losses and Slater's condition. A Lyapunov-drift proof sketch is provided, and a simulation on energy-efficient task processing in data centers is reported.

Significance. The claimed results, if fully proved, would be a useful contribution: optimal-order regret with bandit constraint feedback, no anytime projection, and a computationally simple primal-dual update, improving on the T^{2/3}-type rates of safe-projection methods. The algorithm's design--linearized loss, pessimistic least-squares constraint estimates, and a virtual queue with extra budget pacing--is natural, and the high-level parameter balance is plausible. However, the key lemma's proof has a time-index gap, and the anytime high-probability bound on the virtual queue is only cited, not derived; the significance is therefore conditional on a complete proof being supplied. The simulation alone does not validate the theoretical rates.

major comments (5)
  1. [Section VI, Lemma 1 proof] The proof derives an inequality for V(f_{t-1}(x_{t-1})-f_{t-1}(x)) with the proximal term D(x,x_{t-1},x_t)/(2eta), but Lemma 1 and Eq. (6) state the inequality for V(f_t(x_t)-f_t(x)) with D(x,x_t,x_{t+1})/(2eta). Since the loss sequence is adversarially chosen and f_t is revealed only after x_t is played, convexity and Lipschitzness of each f_t do not justify replacing f_{t-1}(x_{t-1})-f_{t-1}(x) by f_t(x_t)-f_t(x) or shifting the proximal index from (t-1,t) to (t,t+1). Eq. (6) is the step from which the regret telescope (7), the soft-violation O(1) claim, and the hard-budget regret claim all follow, so the central theorem is currently unsupported. A correct proof will require a re-indexed drift argument, for example using the t+1 update and paying for the movement cost, or a modified algorithm in which the gradient used in x_t is nabla f_t(x_t); the latter is not available in the stated feedback model.
  2. [Section V, Eq. (9)] The anytime high-probability bound ||Q_t|| = O(sqrt(T) log T) for all t is asserted by invoking a Foster-Lyapunov lemma from [29] and [65], but the lemma is not stated, its hypotheses are not verified for the present process (Q_t, \bar A_t, \hat g_t), and the constants are not tracked. This bound is the bridge from the drift inequality to the O(1) soft violation and to the hard-budget regret; without a self-contained statement and verification, or at least a precise quotation of a theorem whose assumptions are checked, Theorem 1 is not established. In particular, the later step V(T) <= (E||Q_T||_1 - T xi)_+ requires an expectation bound, while Eq. (9) as written is only a probability bound.
  3. [Section V, hard-budget analysis] The hard-budget regret argument is incomplete. The displayed inequality sum_t g_t(x_t) <= Q_{T+1} + sum_t(g_t(x_t) - \hat g_t(x_t)) relates cumulative consumption to the queue, but it does not by itself bound the regret of an algorithm that may stop early relative to the T-round offline benchmark, and it does not account for the budget consumed during the pure exploration phase of length T0 = log T / beta. The paper needs a precise definition of regret under early termination, a proof that the probability of stopping before T is small, and a bound on the loss difference caused by the unplayed rounds.
  4. [Section V, regret comparison] The regret is first bounded against the time-varying comparator x*_{epsilon_t} in the tightened feasible set X_{epsilon_t}, and then it is asserted that the original regret against x* is O~(sqrt(T)) because sum_t epsilon_t = O~(sqrt(T)). The paper does not prove a stability bound relating sum_t(f_t(x*_{epsilon_t}) - f_t(x*)) to sum_t epsilon_t under Assumptions 1-3; such a bound, for example via Slater's condition and Lipschitzness of f_t, is needed to justify the last step of the regret analysis. The telescoping of the D(x,x_t,x_{t+1}) terms leading to D^2/(V eta) in Eq. (7) should also be written out with the correct indices.
  5. [Section IV, Algorithm 1] The algorithm as stated requires knowledge of the Slater constant beta to set T0 = log T / beta, and it presupposes beta >= log T / T so that T0 <= T; neither condition appears in Assumption 3. In addition, the exploration phase says to generate a scaled Gaussian random vector x_t in X, but for a general convex compact set X this is not well-defined unless X contains a ball or a projection is specified, and the lower bound on the least-squares covariance needed for the confidence bound in (5) is not established.
minor comments (5)
  1. [Theorem 1 and Section V] Theorem 1 sets eta = 1/T, but the regret-analysis paragraph in Section V says 'Recall V = sqrt(T), eta = T'; the proof requires eta = 1/T, so this is a typo to correct.
  2. [Section VI, proof of Lemma 1] The displayed high-probability event has the inequality in the wrong direction: it should be P((\bar A_t - A)x <= -(alpha ||x||_{Sigma_t^{-1}} + xi)1) <= T^{-3} rather than P((\bar A_t - A)x >= (...)).
  3. [Abstract and Theorem 1] The abstract claims zero cumulative constraint violation, while Theorem 1 states V(T) = O(1); the zero-violation conclusion is justified only for sufficiently large T and should be stated with that qualification in both places.
  4. [Section VII] Figure 1 is referenced in Section VII but is not visible in the manuscript text supplied for review; please ensure the figure and its caption are present and specify the number of independent runs and the error bars.
  5. [Model notation] The notation for the budget dimension is inconsistent: the model uses vectors with xi 1 and beta 1, the violation bound uses ||Q_T||_1, and Eq. (9) is stated for the Euclidean norm ||Q_t||; the norm and dimension conventions should be made explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the claimed regret and violation bounds are derived from independently defined benchmarks and standard external concentration tools; the proof's apparent index mismatch in Lemma 1 is a correctness concern, not circularity.

full rationale

The paper's derivation chain is not circular. The regret benchmark is the offline optimum of problem (1)-(2), defined before and independently of the algorithm, and the violation measure is the positive part of cumulative consumption minus budget; neither definition presupposes Theorem 1. The pessimistic constraint estimator (5) and the parameter choices in Theorem 1 (V=sqrt(T), eta=1/T, xi=log^2(T)/sqrt(T), T0=log(T)/beta) are explicit design choices used in the proof, not values fitted to the reported regret or violation curves. The key concentration step 'P((Abar_t-A)x >= (alpha||x||_{Sigma_t^{-1}}+xi)1) <= 1-T^{-3}' is attributed to the external linear-bandit result [57], not to the present authors. The only self-citations ([50], [51], and [65]) are either related-work references or, in the case of [65], one supporting citation for the Forster-Lyapunov technique that is paired with the external reference [29]; they are not the sole load-bearing source. The zero-violation conclusion follows algebraically from the stated high-probability queue bound combined with the xi margin, as V(T) <= (E[||Q_T||_1] - T*xi)^+. No displayed equation is equal to its own input by construction, and no fitted parameter is renamed as a prediction. A separate correctness concern exists: the proof of Lemma 1 derives inequalities involving f_{t-1}(x_{t-1}) - f_{t-1}(x), while the lemma statement requires f_t(x_t) - f_t(x), and the final display silently re-indexes the loss and proximal term; this is an unproved inequality or indexing gap, but it is not circularity. The reliance on a known Slater constant beta for T0 is a modeling limitation, not a circular input.

Assumptions & free parameters 5 free parameters · 5 assumptions · 1 invented entities

The central results rest on standard UCB concentration [57] and on a Forster-Lyapunov drift lemma [29], [65] that is cited rather than proved. The algorithm parameters V, η, ξ, T0, and α are chosen by the authors to optimize the bounds; ξ acts as an explicit safety margin. The virtual queue is an algorithmic construction, not an unsupported physical postulate.

free parameters (5)
  • V = √T
    Lyapunov weight in the primal objective, chosen in Theorem 1 to balance regret and drift.
  • η = 1/T
    Proximal step size in Algorithm 1 line 6; Theorem 1 states η=1/T, while Section V writes η=T in one place.
  • ξ = log²T / √T
    Pessimistic budget-pacing buffer in the virtual queue update; it creates the safety margin that yields zero violation.
  • T0 = log T / β
    Length of the pure exploration phase, which depends on the Slater constant β.
  • α = Θ(√log T + √λ)
    UCB radius in the pessimistic constraint estimate, following the concentration bound in [57].
assumptions (5)
  • domain assumption The feasible set X is convex with diameter D (Assumption 1).
    Boundedness of the decision set is used throughout the regret and violation analysis.
  • domain assumption Losses are convex and F-Lipschitz; A_t are i.i.d. with entries in [0,1]; average budget b ∈ [0,1] (Assumption 2).
    These boundedness and stochastic assumptions are needed for the UCB concentration argument and the Lipschitz bounds in Lemma 1.
  • domain assumption Slater's condition: there exists x with Ax - b ≤ -β1 for some β>0 (Assumption 3).
    Used to set the exploration length T0 and to derive the negative drift term that bounds the virtual queue.
  • standard math The UCB concentration bound of Abbasi-Yadkori et al. [57] holds for the ridge-regression estimate of A.
    Invoked to construct the pessimistic constraint function \\hat g_t in equation (5) and to control the cross term in Lemma 1.
  • standard math The Forster-Lyapunov lemma from [29] and [65] justifies the anytime high-probability bound on the virtual queue.
    Equation (9) relies on this multi-step Lyapunov analysis, but the lemma is cited rather than stated or proved in the paper.
invented entities (1)
  • Virtual queue Q_t
    purpose: Tracks cumulative pessimistic over-consumption and acts as the dual variable in the primal-dual update.
    This is an algorithmic device defined by the queue update, not a claimed empirical entity. No independent evidence is needed because it is not asserted to exist outside the algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback." pith.science (2026). https://pith.science/paper/TZFYSHAV

@misc{pith2026241203983,
  author       = {Pith},
  title        = {Pith review of: Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TZFYSHAV}},
  note         = {Machine review of arXiv:2412.03983}
}
abstract

This paper studies online convex optimization with unknown linear budget constraints, where only the gradient information of the objective and the bandit feedback of constraint functions are observed. We propose a safe and efficient Lyapunov-optimization algorithm (SELO) that can achieve an $O(\sqrt{T})$ regret and zero cumulative constraint violation. The result also implies SELO achieves $O(\sqrt{T})$ regret when the budget is hard and not allowed to be violated. The proposed algorithm is computationally efficient as it resembles a primal-dual algorithm where the primal problem is an unconstrained, strongly convex and smooth problem, and the dual problem has a simple gradient-type update. The algorithm and theory are further justified in a simulated application of energy-efficient task processing in distributed data centers.

Figures

Figures reproduced from arXiv: 2412.03983 by the authors.

Figure 1
Figure 1. Performance comparison: SELO v.s. “AnytimeSafe”. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

70 extracted references · 63 canonical work pages

  1. [20]

    Safe online convex optimization with unknown linear safety constraints,

    S. Chaudhary and D. Kalathil, “Safe online convex optimization with unknown linear safety constraints,” Proceedings of the AAAI Conference on Artificial Intelligence , 2022

    work page 2022

  2. [29]

    Online convex optimization with stochas- tic constraints,

    H. Yu, M. Neely, and X. Wei, “Online convex optimization with stochas- tic constraints,” Advances in Neural Information Processing Systems , vol. 30, 2017

    2017

  3. [65]

    An efficient pessimistic-optimistic algorithm for stochastic linear bandits with general constraints,

    X. Liu, B. Li, P. Shi, and L. Ying, “An efficient pessimistic-optimistic algorithm for stochastic linear bandits with general constraints,” in Advances in Neural Information Processing Systems , 2021

    work page 2021

  4. [1]

    Online learning and online convex optimization,

    S. Shalev-Shwartz, “Online learning and online convex optimization,” Found. Trends Mach. Learn., vol. 4, no. 2, p. 107–194, 2012

    work page 2012

  5. [2]

    Introduction to online convex optimization,

    E. Hazan, “Introduction to online convex optimization,” Foundations and Trends® in Optimization, vol. 2, no. 3-4, pp. 157–325, 2016

    work page 2016

  6. [3]

    A modern introduction to online learning,

    F. Orabona, “A modern introduction to online learning,” arXiv preprint arXiv:1912.13213, 2019

    arXiv 1912

  7. [4]

    An online learning approach to model predictive control,

    N. Wagener, C.-A. Cheng, J. Sacks, and B. Boots, “An online learning approach to model predictive control,” 2019

    work page 2019

  8. [5]

    Dual Online Stein Variational Inference for Control and Dynamics,

    Barcelos, Lucas and Lambert, Alexander and Oliveira, Rafael and Borges, Paulo and Boots, Byron and Ramos, Fabio, “Dual Online Stein Variational Inference for Control and Dynamics,” in Robotics: Science and Systems (R:SS) , 2021

    work page 2021

Show all 70 references
  1. [6]

    Learning to Optimize in Model Predictive Control,

    Sacks, Jacob and Boots, Byron, “Learning to Optimize in Model Predictive Control,” in IEEE International Conference on Robotics and Automation (ICRA), 2022

    2022

  2. [7]

    An online convex optimization approach to proactive network resource allocation,

    T. Chen, Q. Ling, and G. B. Giannakis, “An online convex optimization approach to proactive network resource allocation,” IEEE Transactions on Signal Processing , vol. 65, no. 24, pp. 6350–6364, 2017

    2017

  3. [8]

    Stochastic averaging for constrained optimization with application to online resource allocation,

    T. Chen, A. Mokhtari, X. Wang, A. Ribeiro, and G. B. Giannakis, “Stochastic averaging for constrained optimization with application to online resource allocation,” IEEE Transactions on Signal Processing , 2017

    2017

  4. [9]

    Bregman-style online convex optimization with energyharvesting constraints,

    K. Asgari and M. J. Neely, “Bregman-style online convex optimization with energyharvesting constraints,” Proc. ACM Meas. Anal. Comput. Syst. (POMACS), 2020

    2020

  5. [10]

    Learning-aided optimization for energy- harvesting devices with outdated state information,

    H. Yu and M. J. Neely, “Learning-aided optimization for energy- harvesting devices with outdated state information,” IEEE/ACM Trans- actions on Networking , vol. 27, no. 4, pp. 1501–1514, 2019

    2019

  6. [11]

    Distributed constrained online convex optimiza- tion over multiple access fading channels,

    X. Cao and T. Bas ¸ar, “Distributed constrained online convex optimiza- tion over multiple access fading channels,” IEEE Transactions on Signal Processing, 2022

    2022

  7. [12]

    Pobo: Safe and optimal re- source management for cloud microservices,

    H. Guo, H. Cao, J. He, X. Liu, and Y . Shi, “Pobo: Safe and optimal re- source management for cloud microservices,” Performance Evaluation, 2023

    2023

  8. [13]

    A virtual-queue-based algorithm for constrained online convex optimization with applications to data center resource allocation,

    X. Cao, J. Zhang, and H. V . Poor, “A virtual-queue-based algorithm for constrained online convex optimization with applications to data center resource allocation,” IEEE Journal of Selected Topics in Signal Processing, 2018

    2018

  9. [14]

    Integrated online learning and adaptive control in queueing systems with uncertain payoffs,

    W.-K. Hsu, J. Xu, X. Lin, and M. R. Bell, “Integrated online learning and adaptive control in queueing systems with uncertain payoffs,” Operations Research, vol. 70, no. 2, pp. 1166–1181, 2022

    2022

  10. [15]

    Matching while learning,

    R. Johari, V . Kamble, and Y . Kanoria, “Matching while learning,” Operations Research, vol. 69, no. 2, pp. 655–681, 2021

    2021

  11. [16]

    Ad click prediction: A view from the trenches,

    H. B. McMahan, G. Holt, D. Sculley, M. Young, D. Ebner, J. Grady, L. Nie, T. Phillips, E. Davydov, D. Golovin, S. Chikkerur, D. Liu, M. Wattenberg, A. M. Hrafnkelsson, T. Boulos, and J. Kubica, “Ad click prediction: A view from the trenches,” KDD, 2013

    2013

  12. [17]

    Dual mirror descent for online al- location problems,

    S. Balseiro, H. Lu, and V . Mirrokni, “Dual mirror descent for online al- location problems,” in Proceedings of the 37th International Conference on Machine Learning , PMLR, 2020

    2020

  13. [18]

    Per- sonalized hospital admission control: A contextual learning approach,

    M. Zhalechian, E. Keyvanshokooh, C. Shi, and M. P. Van Oyen, “Per- sonalized hospital admission control: A contextual learning approach,” Available at SSRN 3653433 , 2020

    2020

  14. [19]

    Tewari and S

    A. Tewari and S. A. Murphy, From Ads to Interventions: Contextual Bandits in Mobile Health . Springer International Publishing, 2017

    2017

  15. [21]

    Dynamic regret analysis of safe distributed online optimization for convex and non-convex problems,

    T.-J. Chang, S. Chaudhary, D. Kalathil, and S. Shahrampour, “Dynamic regret analysis of safe distributed online optimization for convex and non-convex problems,” Transactions on Machine Learning Research , 2023

    2023

  16. [22]

    Linear stochastic bandits under safety constraints,

    S. Amani, M. Alizadeh, and C. Thrampoulidis, “Linear stochastic bandits under safety constraints,” in Advances in Neural Information Processing Systems, 2019

    2019

  17. [23]

    Linear thompson sampling under unknown linear constraints,

    A. Moradipari, M. Alizadeh, and C. Thrampoulidis, “Linear thompson sampling under unknown linear constraints,” in ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Pro- cessing (ICASSP), 2020

    2020

  18. [24]

    Generalized linear ban- dits with safety constraints,

    S. Amani, M. Alizadeh, and C. Thrampoulidis, “Generalized linear ban- dits with safety constraints,” in ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020

    2020

  19. [25]

    Safe linear thompson sampling with side information,

    A. Moradipari, S. Amani, M. Alizadeh, and C. Thrampoulidis, “Safe linear thompson sampling with side information,” IEEE Transactions on Signal Processing , 2021

    2021

  20. [26]

    Optimistic safety for online convex optimization with unknown linear constraints,

    S. Hutchinson, T. Chen, and M. Alizadeh, “Optimistic safety for online convex optimization with unknown linear constraints,” 2024

    2024

  21. [27]

    Trading regret for efficiency: online convex optimization with long term constraints,

    M. Mahdavi, R. Jin, and T. Yang, “Trading regret for efficiency: online convex optimization with long term constraints,”The Journal of Machine Learning Research, vol. 13, no. 1, pp. 2503–2528, 2012

    2012

  22. [28]

    Safety-aware algorithms for adversarial contextual bandit,

    W. Sun, D. Dey, and A. Kapoor, “Safety-aware algorithms for adversarial contextual bandit,” in International Conference on Machine Learning , pp. 3280–3288, PMLR, 2017

    2017

  23. [30]

    Online convex optimization with time-varying constraints,

    M. J. Neely and H. Yu, “Online convex optimization with time-varying constraints,” arXiv preprint arXiv:1702.04783 , 2017

    2017 arXiv

  24. [31]

    Cautious regret minimization: Online optimization with long-term budget constraints,

    N. Liakopoulos, A. Destounis, G. Paschos, T. Spyropoulos, and P. Mer- tikopoulos, “Cautious regret minimization: Online optimization with long-term budget constraints,” in Proceedings of the 36th International Conference on Machine Learning , 2019

    2019

  25. [32]

    Online stochastic optimization with time-varying distributions,

    X. Cao, J. Zhang, and H. V . Poor, “Online stochastic optimization with time-varying distributions,” IEEE Transactions on Automatic Control , vol. 66, no. 4, pp. 1840–1847, 2021

    2021

  26. [33]

    A single recipe for online submodu- lar maximization with adversarial or stochastic constraints,

    O. Sadeghi, P. Raut, and M. Fazel, “A single recipe for online submodu- lar maximization with adversarial or stochastic constraints,” in Advances in Neural Information Processing Systems , 2020

    2020

  27. [34]

    Online convex optimization for cumula- tive constraints,

    J. Yuan and A. Lamperski, “Online convex optimization for cumula- tive constraints,” Advances in Neural Information Processing Systems , vol. 31, 2018

    2018

  28. [35]

    Regret and cumulative constraint violation analysis for online convex optimization with long term constraints,

    X. Yi, X. Li, T. Yang, L. Xie, T. Chai, and K. Johansson, “Regret and cumulative constraint violation analysis for online convex optimization with long term constraints,” in International Conference on Machine Learning, pp. 11998–12008, PMLR, 2021

    2021

  29. [36]

    Online convex optimization with hard constraints: Towards the best of two worlds and beyond,

    H. Guo, X. Liu, H. Wei, and L. Ying, “Online convex optimization with hard constraints: Towards the best of two worlds and beyond,” in Advances in Neural Information Processing Systems , 2022

    2022

  30. [37]

    Online nonstochastic control with adver- sarial and static constraints,

    X. Liu, Z. Yang, and L. Ying, “Online nonstochastic control with adver- sarial and static constraints,” in Proceedings of the 40th International Conference on Machine Learning , 2023

    2023

  31. [38]

    Optimal algorithms for online convex optimiza- tion with adversarial constraints,

    A. Sinha and R. Vaze, “Optimal algorithms for online convex optimiza- tion with adversarial constraints,” in Advances in Neural Information Processing Systems, 2024

    2024

  32. [39]

    Bandits with knap- sacks,

    A. Badanidiyuru, R. Kleinberg, and A. Slivkins, “Bandits with knap- sacks,” in Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , FOCS ’13, 2013

    2013

  33. [40]

    Bandits with knap- sacks,

    A. Badanidiyuru, R. Kleinberg, and A. Slivkins, “Bandits with knap- sacks,” Journal of the ACM (JACM) , vol. 65, no. 3, pp. 1–55, 2018

    2018

  34. [41]

    Resourceful contextual bandits,

    A. Badanidiyuru, J. Langford, and A. Slivkins, “Resourceful contextual bandits,” in Conference on Learning Theory , pp. 1109–1134, PMLR, 2014

    2014

  35. [42]

    Linear contextual bandits with knapsacks,

    S. Agrawal and N. Devanur, “Linear contextual bandits with knapsacks,” Advances in Neural Information Processing Systems , vol. 29, 2016

    2016

  36. [43]

    Ad- versarial bandits with knapsacks,

    N. Immorlica, K. Sankararaman, R. Schapire, and A. Slivkins, “Ad- versarial bandits with knapsacks,” Journal of the ACM , vol. 69, no. 6, pp. 1–47, 2022

    2022

  37. [44]

    Smoothed adversarial linear contextual bandits with knapsacks,

    V . Sivakumar, S. Zuo, and A. Banerjee, “Smoothed adversarial linear contextual bandits with knapsacks,” in Proceedings of the 39th Interna- tional Conference on Machine Learning , 2022

    2022

  38. [45]

    Bandits with replenishable knapsacks: the best of both worlds,

    M. Bernasconi, M. Castiglioni, A. Celli, and F. Fusco, “Bandits with replenishable knapsacks: the best of both worlds,” in The Twelfth International Conference on Learning Representations , 2024

    2024

  39. [46]

    Fair contextual multi-armed bandits: Theory and experiments,

    Y . Chen, A. Cuellar, H. Luo, J. Modi, H. Nemlekar, and S. Nikolaidis, “Fair contextual multi-armed bandits: Theory and experiments,” in Pro- ceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), 2020

    2020

  40. [47]

    Banditq: Fair bandits with guaranteed rewards,

    A. Sinha, “Banditq: Fair bandits with guaranteed rewards,” in The 40th Conference on Uncertainty in Artificial Intelligence , 2024

    2024

  41. [48]

    Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression,

    A. Slivkins, K. A. Sankararaman, and D. J. Foster, “Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression,” in Annual Conference Computational Learning Theory , 2023

    2023

  42. [49]

    Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression,

    A. Slivkins, X. Zhou, K. A. Sankararaman, and D. J. Foster, “Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression,” Journal of Machine Learning Research, 2024

    2024

  43. [50]

    Stochastic constrained contextual bandits via lyapunov optimization based estimation to decision framework,

    H. Guo and X. Liu, “Stochastic constrained contextual bandits via lyapunov optimization based estimation to decision framework,” in Pro- ceedings of Thirty Seventh Conference on Learning Theory, Proceedings of Machine Learning Research, 2024

    2024

  44. [51]

    On stochastic contextual bandits with knapsacks in small budget regime,

    H. Guo and X. Liu, “On stochastic contextual bandits with knapsacks in small budget regime,” in The Thirteenth International Conference on Learning Representations, 2025

    2025

  45. [52]

    Stochastic bandits with linear constraints,

    A. Pacchiano, M. Ghavamzadeh, P. Bartlett, and H. Jiang, “Stochastic bandits with linear constraints,” in Proceedings of The 24th International Conference on Artificial Intelligence and Statistics , 2021

    2021

  46. [53]

    Strategies for safe multi- armed bandits with logarithmic regret and risk,

    T. Chen, A. Gangrade, and V . Saligrama, “Strategies for safe multi- armed bandits with logarithmic regret and risk,” in Proceedings of the 39th International Conference on Machine Learning , Proceedings of Machine Learning Research, 2022

    2022

  47. [54]

    Safe linear bandits over unknown polytopes,

    A. Gangrade, T. Chen, and V . Saligrama, “Safe linear bandits over unknown polytopes,” in Proceedings of Thirty Seventh Conference on Learning Theory, 2024

    2024

  48. [55]

    Testing the feasibility of linear programs with bandit feedback,

    A. Gangrade, A. Gopalan, V . Saligrama, and C. Scott, “Testing the feasibility of linear programs with bandit feedback,” in Proceedings of the 41st International Conference on Machine Learning , Proceedings of Machine Learning Research, 2024

    2024

  49. [56]

    Finite-time analysis of the multiarmed bandit problem,

    P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” Mach. Learn., 2002

    2002

  50. [57]

    Improved algorithms for linear stochastic bandits,

    Y . Abbasi-yadkori, D. P ´al, and C. Szepesv ´ari, “Improved algorithms for linear stochastic bandits,” in Advances in Neural Information Processing Systems 24, 2011

    2011

  51. [58]

    Lattimore and C

    T. Lattimore and C. Szepesv ´ari, Bandit Algorithms. Cambridge Univer- sity Press, 2020

    2020

  52. [59]

    Stochastic network optimization with application to communication and queueing systems,

    M. J. Neely, “Stochastic network optimization with application to communication and queueing systems,” Synthesis Lectures on Commu- nication Networks, vol. 3, no. 1, pp. 1–211, 2010

    2010

  53. [60]

    Srikant and L

    R. Srikant and L. Ying, Communication Networks: An Optimization, Control and Stochastic Networks Perspective . Cambridge University Press, 2014

    2014

  54. [61]

    Boyd and L

    S. Boyd and L. Vandenberghe, Convex optimization. Cambridge univer- sity press, 2004

    2004

  55. [62]

    Convergence rates of inexact proximal-gradient methods for convex optimization,

    M. Schmidt, N. Roux, and F. Bach, “Convergence rates of inexact proximal-gradient methods for convex optimization,” in Advances in Neural Information Processing Systems , vol. 24, 2011

    2011

  56. [63]

    Online convex programming and generalized infinitesi- mal gradient ascent,

    M. Zinkevich, “Online convex programming and generalized infinitesi- mal gradient ascent,” in Proceedings of the 20th International Confer- ence on Machine Learning , pp. 928–936, 2003

    2003

  57. [64]

    Projection-free online learning,

    E. Hazan and S. Kale, “Projection-free online learning,” in Proceedings of the 29th International Coference on International Conference on Machine Learning, 2012

    2012

  58. [66]

    Convergence analysis of a proximal-like minimization algorithm using bregman functions,

    G. Chen and M. Teboulle, “Convergence analysis of a proximal-like minimization algorithm using bregman functions,” SIAM Journal on Optimization, vol. 3, no. 3, pp. 538–543, 1993

    1993

  59. [67]

    A low complexity algorithm with O( √ T ) regret and O(1) constraint violations for online convex optimization with long term constraints,

    H. Yu and M. J. Neely, “A low complexity algorithm with O( √ T ) regret and O(1) constraint violations for online convex optimization with long term constraints,” The Journal of Machine Learning Research , vol. 21, no. 1, pp. 1–24, 2020

    2020

  60. [68]

    On the convergence rates of policy gradient methods,

    L. Xiao, “On the convergence rates of policy gradient methods,” arXiv preprint arXiv:2201.07443, 2022

    2022 arXiv

  61. [69]

    Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

    M. Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, 2013

    2013

  62. [70]

    New york ISO open access pricing data.,

    “New york ISO open access pricing data.,” http://www.nyiso.com/

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.