Pith. sign in

REVIEW 3 major objections 5 minor 41 references

Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint

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

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

Pith's one-line read This paper proves that any online auto-bidding algorithm that strictly satisfies a return-on-spend constraint suffers linear regret, even when the input is i.i.d. and the allocation and payment functions are structured.

desk verdict The headline impossibility result (Theorem 5) is unsupported: the two-input construction is infeasible as stated, and the rest of the paper is a mixed bag of solid constant-v results and a near-optimal algorithm whose proof leans on an unverified queue analogy. read the letter →

arxiv 2502.05599 v2 pith:Y2NZ4LDQ submitted 2025-02-08 cs.GT cs.DScs.LG

Rahul Vaze , Abhishek Sinha This is my paper · ORCID
classification cs.GTcs.DScs.LG MSC 68W2791B26
keywords auto-biddingreturn-on-spendconstraintonlinealgorithmsregretlowerboundcompetitiveratiorepeatedidenticalauctionthresholdallocationfunctionsstochastici.i.d.input
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

The paper studies online auto-bidding, where in each round an algorithm sees an ad's value, places a bid, and only afterwards learns the hidden probability of winning and the expected payment that its bid produced, subject to a strict return-on-spend constraint that total expected payment never exceed total expected value. Its principal result is that under this strict constraint no online algorithm can have sublinear regret, even when the value-allocation-payment triples are drawn i.i.d. from an unknown distribution; only a constant slack in the constraint buys sublinear regret. The paper also proves that the problem is nontrivial when the value is fixed across rounds, with regret plus constraint violation necessarily at least on the order of the square root of the horizon, and it provides an algorithm whose regret is within a logarithmic factor of that lower bound for threshold allocation functions. For the general i.i.d. case it turns to the competitive-ratio metric and gives a simple algorithm that is nearly 1/2-competitive while satisfying the return-on-spend constraint with high probability.

What carries the argument

The lower-bound constructions use threshold allocation and payment functions $x_t(b)=\mathbb{1}\{b\ge \theta_t\}$ and $p_t(b)=\theta_t\mathbb{1}\{b\ge \theta_t\}$, which satisfy the standard payment identity, and pit two inputs whose distributions are close in relative entropy so that no online algorithm can reliably distinguish them while the offline optimum differs sharply. For the positive result, the algorithm $A_c$ bids $b_t = v + \mathrm{Margin}(t-1)/\sqrt{T}$, where $\mathrm{Margin}(t)$ is the running total of past per-slot surplus (value minus payment), capped at zero; this reflected random walk is shown, under a queueing-model concentration bound, to reach and then hover near the optimal threshold $\theta^{\star}$ quickly, causing only $O(\sqrt{T}\log T)$ lost slots. The competitive-ratio algorithm learns the distribution in the first half of the horizon and then applies the threshold rule from a knapsack-like linear program.

What would settle it

Compute the relative entropy between the two input distributions in the lower-bound construction with $\epsilon = 1/\sqrt{T}$; if it grows faster than $O(1)$ as $T$ increases, the linear-regret lower bound collapses. Separately, simulate algorithm $A_c$ on the repeated identical auction with thresholds from Example 3 over growing horizons: if its regret is $\Theta(T)$ rather than $O(\sqrt{T}\log T)$, the queueing-model analogy used in the proof is invalid.

Watch

Extended reading notes

Core claim

The paper's central claim is an impossibility: for the auto-bidding problem with a strict return-on-spend constraint, every online algorithm has regret linear in the horizon $T$, even when the value-allocation-payment triple is drawn i.i.d. from an unknown distribution and the allocation and payment functions are of a simple threshold type satisfying the standard payment identity. The lower bound relies on two statistically close inputs for which the offline optimum behaves very differently. Because bidding the revealed value in every slot trivially satisfies the ROSC and already has linear regret, strict constraint satisfaction makes the naive algorithm order-wise optimal. In the restricted setting where the value is constant across slots, the paper proves the sum of regret and expected constraint violation is at least $c\sqrt{T}$, and it constructs an algorithm whose regret is $O(\sqrt{T}\log T)$ for threshold allocation functions, achieving the lower bound up to logarithmic factors.

Load-bearing premise

The impossibility result assumes the two constructed input distributions are nearly indistinguishable yet force very different optimal behavior, and the near-optimal algorithm assumes its Margin process satisfies a standard queueing concentration bound with a drift that does not shrink as the horizon grows.

Editorial extensions

If this is right

  • Strictly satisfying the return-on-spend constraint forces $\Omega(T)$ regret, so any practical sublinear-regret auto-bidder must allow a tunable amount of constraint violation.
  • The naive bid-the-value policy is order-wise optimal among strictly feasible online algorithms, making it a stronger baseline than previously thought.
  • In the repeated identical auction, the proposed algorithm $A_c$ attains the $\Omega(\sqrt{T})$ lower bound up to a $O(\log T)$ factor, so the constant-value problem is essentially resolved for threshold allocation functions.
  • The existing primal-dual algorithm with claimed $O(\sqrt{T})$ regret has regret at least $\Omega(\sqrt{T})$ in the constant-value setting, so its regret guarantee is tight even though it violates the ROSC.
  • For non-constant values, a competitive ratio arbitrarily close to $1/2$ is achievable with high-probability ROSC satisfaction after a learning phase.

Reading between the lines

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

  • If the linear-regret impossibility is robust, then the right performance measure for strict-ROSC auto-bidding is competitive ratio, not regret; the paper's $1/2$-competitive algorithm is a first step toward characterizing the best achievable ratio.
  • The indistinguishability construction (two relative-entropy-close inputs) likely transfers to other online optimization problems with binding expected-value constraints, suggesting that exact feasibility and sublinear regret are generally incompatible when the constraint is hidden.
  • A natural testable extension is to run algorithm $A_c$ on non-threshold allocation functions; if its bid process still concentrates near a critical bid level, the $O(\sqrt{T}\log T)$ guarantee may extend beyond the threshold class.
  • Closing the gap between the known $O(\sqrt{T})$ regret with $O(\sqrt{T}\log T)$ ROSC violation and the new $\Omega(\sqrt{T})$ sum lower bound is left open; a stronger violation lower bound would settle the best simultaneous tradeoff.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies an online auto-bidding problem in which an algorithm observes a value vt, places a bid, and receives only the resulting allocation and payment, all under a strict expected return-on-spend constraint (ROSC). The central claimed result is an impossibility theorem (Theorem 5): no online algorithm that satisfies the ROSC in expectation can have sublinear regret even under i.i.d. draws from an unknown distribution. For the special case of a constant value vt=v, the paper claims a lower bound of Ω(√T) on the sum of regret and ROSC violation (Theorem 8), a matching near-optimal algorithm with O(√T log T) regret for threshold allocation functions (Theorem 12), and, for general i.i.d. values, a 1/2-competitive algorithm (Theorem 19). The proofs use pairs of statistically close input distributions and, for the upper bound, a queueing comparison. The claimed impossibility result is the main load-bearing contribution; the constant-value lower bound and the proposed algorithm are secondary contributions.

Significance. If Theorem 5 were correct, it would be a striking result: it would rule out sublinear regret for any algorithm that exactly respects the ROSC in the i.i.d. stochastic setting, thereby showing that prior sublinear-regret algorithms necessarily rely on constraint violation. The paper also contains useful conceptual distinctions between regret and cumulative constraint violation, and the proposed algorithm Ac does satisfy the ROSC on a sample-path basis rather than only in expectation. Each lower-bound construction is explicit and the paper does not fit parameters to data. However, the central impossibility proof is not sound as written: the two constructed input distributions have mutually contradictory parameter constraints, so the Bretagnolle-Huber argument is applied to an empty family of instances. In addition, the O(√T log T) upper-bound proof relies on a queueing analogy whose required assumptions are not verified and whose drift sign appears inconsistent with Assumption 15. These are load-bearing failures in the main claims, and they require new proof ideas rather than local corrections.

major comments (3)
  1. [Section 10 (proof of Theorem 5)] The two constructed input distributions are infeasible under the stated parameter ranges. Input 1 requires a+(1-r)b=ε, while Input 2 requires a+(1-r+δ)b=4ε, with 0≤δ≤r<1/2, a,b≥0, and v2+b≤1. Subtracting the two equations gives δb=3ε. From a≥0 and a+(1-r)b=ε we get b≤ε/(1-r), and since 1-r>1/2 this implies δ≥3(1-r)>3/2, contradicting δ≤r<1/2. Thus no choice of a,b,r,δ satisfies the construction. This is not a cosmetic typo: keeping δ=O(1/√T) forces the ratio (a+E[X'])/(a+E[X]) to tend to 1, while Lemma 21 requires this ratio to be a constant (4) exceeding v2/v1=1.8. Hence the proof of the Ω(T) lower bound in Theorem 5 is unsupported as written.
  2. [Section 12 (Lemma 27, proof of Theorem 12)] The claimed O(√T log T) regret bound depends on Lemma 27, which asserts that the Margin process of algorithm Ac is analogous to the controlled queue (16)-(17) and then applies [32, Lemma 2]. The mapping is not verified: the increments of the Margin process are state-dependent, because a negative jump (v-θ) occurs only when the current bid is high enough, i.e. Margin(t-1) ≥ √T(θ-v); this self-exciting dependence is not present in the queue model, whose arrivals A(t) are exogenous. Moreover, the drift above threshold has the wrong sign. With Δ=μL+μ_R^{θ*} >0, Assumption 15 gives |μbar_R^{θ*}|≤|μ_R^{θ*}|, so μL+μbar_R^{θ*} ≥ Δ>0; the expected increment above θ* is therefore positive, whereas the queue model (17) requires a negative net drift above U/2. Consequently the bound P(bt<(1-δ)θ*)≤exp(-δΔθ*√T c) is not established, and the regret bound of Theorem 12 is unsupported.
  3. [Section 11 (proof of Theorem 8)] The proof asserts, after the two inputs are defined, that 'WLOG, we let any A only bid either bt=C or bt=D for all t.' This restriction is load-bearing: the event E is defined in terms of the number of C/D bids, and Lemmas 23-25 compute the expected CCV only for those two actions. No argument is given that an arbitrary online algorithm can be restricted to this binary action set without losing regret or changing the expected constraint violation. If the restriction is intended as a dominance argument, it needs to be stated and proved; otherwise the lower bound in Theorem 8 applies only to a restricted class of algorithms.
minor comments (5)
  1. [Section 8 (Theorem 19)] The displayed bound μLearn-Alg ≥ 1/2 − (1 − O(K log(1/δ)/√T)) is negative for small error terms and cannot be the intended statement. The proof suggests the intended bound is 1/2 − O(K log(1/δ)/√T), so the displayed inequality should be corrected.
  2. [Section 8] The notation 'Plight' for the parameter tuple {K, pk, wk, rk, lk} is awkward and should be replaced by a standard symbol such as P, and the definition should be set off more clearly.
  3. [Throughout] There are several typos and infelicities: 'acrued valuation' for 'accrued valuation', 'acrued value' in Corollary 22, and the phrase 'anon' appears without meaning. These should be cleaned up.
  4. [Section 10] In the expression for the expected accrued valuation of A under Input 1, the factor r from the probability of X=0 is omitted from the v2g2T/2 term. This omission happens to yield an upper bound, but it should be explicitly written as an inequality.
  5. [Section 7, Definition 17] The notation Tθ*, T+θ*, and T-θ* should define the dependence on t more explicitly; as written, it is easy to confuse the set of slot indices with the threshold value θ*.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's bounds are derived from explicit input constructions and external lemmas; the Appendix 10 parameter inconsistency is a correctness issue, not a circular reduction.

full rationale

I walked the derivation chain and found no step in which a claimed prediction or first-principles result reduces, by construction, to its own inputs. Theorem 5's lower bound is built from two explicitly defined input distributions with a KL-divergence argument; the two inputs are chosen to be hard to distinguish while yielding different OPT behavior, and no parameter is fitted to the target regret bound. Theorem 8 uses the same standard two-input KL technique. Theorem 12's upper bound is derived from scratch, with external results [31, 32, 34] used as analytical tools; Assumption 15 explicitly invokes [32, Lemma 2] as an external queueing bound, not as a self-citation that pre-imposes the conclusion. Assumptions 14 and 15 are stated and their necessity is discussed by the authors, including the warning that if Delta = 1/T, the bid takes Omega(T) time to cross the threshold. The paper's self-citations ([21], [26]) appear only in the related-problems discussion or as textbook references for standard concepts (online algorithms, competitive ratio), and they are not load-bearing. One serious concern is that the numerical parameters in the Appendix 10 construction of Theorem 5 appear infeasible: subtracting the two equations a+(1-r)b = epsilon and a+(1-r+delta)b = 4epsilon gives delta b = 3epsilon, while a >= 0 and r < 1/2 force b <= epsilon/(1-r) < 2epsilon, so delta > 3/2, contradicting delta <= r < 1/2. That is a mathematical-error or correctness risk in the lower-bound proof, but it is not a circularity: the proof is not assuming its conclusion, and the claimed reduction is not an input-output equivalence. Since no load-bearing circular step exists, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new physical or model entities; the adversarial distributions are proof constructions, not postulated entities. The central reliance is on the auction model assumptions and on the technical Assumptions 14 and 15 for the upper bound, plus the unproved queue analogy in Lemma 27.

assumptions (6)
  • domain assumption Input distribution D is i.i.d. and unknown; OPT knows D and solves (2).
    Section 2 defines the stochastic model and the benchmark. The lower bound is against this distributional benchmark, not against an offline algorithm with realized functions.
  • domain assumption Allocation and payment functions satisfy monotonicity, xt(0)=0, and pt(vt) <= vt xt(vt) (eq. 1); lower bounds use threshold functions (5) satisfying Myerson's condition (6).
    These are the auction model assumptions. The threshold class is a special case, so lower bounds over it apply to the general model.
  • domain assumption Assumption 14: the drift Delta = mu_L + mu^theta*_R does not depend on T.
    Section 7, Assumption 14. Required for the O(sqrt(T) log T) regret bound of Ac; if Delta = 1/T the bid crosses the threshold in Omega(T) time.
  • domain assumption Assumption 15: |bar-mu^theta*_R| <= |mu^theta*_R|.
    Section 7, Assumption 15. Technical condition used in Lemma 27 to control excursions of the Margin process.
  • ad hoc to paper The Margin process of Ac satisfies the conditions of [32, Lemma 2] (existence of the asymptotic semi-invariant log moment generating function, well-behaved arrivals).
    Invoked in Lemma 27 to obtain the exponential concentration bound. Not proved; the increments are state-dependent.
  • ad hoc to paper WLOG any online algorithm in the Theorem 8 proof only bids C or D.
    Appendix 11 asserts this without proof. Bids between B and C are not analyzed; the equivalence is not established.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint." pith.science (2026). https://pith.science/paper/Y2NZ4LDQ

@misc{pith2026250205599,
  author       = {Pith},
  title        = {Pith review of: Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y2NZ4LDQ}},
  note         = {Machine review of arXiv:2502.05599}
}
read the original abstract

Auto-bidding problem under a strict return-on-spend constraint (ROSC) is considered, where an algorithm has to make decisions about how much to bid for an ad slot depending on the revealed value, and the hidden allocation and payment function that describes the probability of winning the ad-slot depending on its bid. The objective of an algorithm is to maximize the expected utility (product of ad value and probability of winning the ad slot) summed across all time slots subject to the total expected payment being less than the total expected utility, called the ROSC. A (surprising) impossibility result is derived that shows that no online algorithm can achieve a sub-linear regret even when the value, allocation and payment function are drawn i.i.d. from an unknown distribution. The problem is non-trivial even when the revealed value remains constant across time slots, and an algorithm with regret guarantee that is optimal up to logarithmic factor is derived.

Figures

Figures reproduced from arXiv: 2502.05599 by the authors.

Figure 1
Figure 1. Bid Profiles for algorithm Ab and Ac for Example 3. where Margin(t − 1) has been defined in Definition 1. Using Example 3, we next show that RAb (T) = Ω(T). Let the allocation function be of type (5), where Ab wins a slot if bt ≥ θt. Since vt is a constant, any algorithm is just trying to maximize the number of slots it can win while satisfying the ROSC. First we describe the OPT. For the input defined in Example 3,… view at source ↗
Figure 2
Figure 2. Input used to prove Theorem 5. 10. Proof of Theorem 5 Proof: Let vt take two values {v1, v2} = {0.5, 0.9} with equal probability for all t. The allocation functions are x θt t (of type (5)) where θt are distributed as follows. Input 1: If for slot t, vt = v1, then θt ∈ {vt ±ϵ} with equal probability, where 0 < ϵ small. Moreover, if for slot t, vt = v2, then θt = vt+a+X where X ∈ {0, b} with probability r, 1−r, respe… view at source ↗
Figure 3
Figure 3. Input used to prove Theorem 8. since v2 = 0.9 and v1 = 0.5 for some constant c < 1. Recall that with Input 1, the total accrued valuation for OPT is at least v1T 4 + v2T 4 . Thus, when event E happens (NA = o(T)), R1 A(T) ≥  v2(1 − c)T 4  P 1 (E) > Ω(T)P 1 (E). However, if E c is true, then g3 > c1 (for some constant c1) for A, in which case Corollary 22 implies that either the ROSC is violated by A or the regret … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 37 canonical work pages

  1. [8]

    Z. Feng, S. Padmanabhan, D. Wang, Online bidding algorithms for return-on-spend constrained advertisers?, in: Proceedings of the ACM Web Conference 2023, 2023, pp. 3550–3560

    work page 2023

  2. [1]

    S. R. Balseiro, Y . Gur, Learning in repeated auctions with budgets: Regret minimization and equilibrium, Management Science 65 (9) (2019) 3952–3968

    work page 2019

  3. [2]

    Aggarwal, A

    G. Aggarwal, A. Badanidiyuru, A. Mehta, Autobidding with constraints, in: Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY , USA, December 10–12, 2019, Proceedings 15, Springer, 2019, pp. 17–30

    work page 2019

  4. [3]

    Babaioff, R

    M. Babaioff, R. Cole, J. Hartline, N. Immorlica, B. Lucier, Non-quasi-linear agents in quasi-linear mechanisms, arXiv preprint arXiv:2012.02893 (2020). 11

    arXiv 2020

  5. [4]

    Golrezaei, I

    N. Golrezaei, I. Lobel, R. Paes Leme, Auction design for roi-constrained buyers, in: Proceedings of the Web Conference 2021, 2021, pp. 3941–3952

    work page 2021

  6. [5]

    Y . Deng, J. Mao, V . Mirrokni, S. Zuo, Towards efficient auctions in an auto-bidding world, in: Proceedings of the Web Conference 2021, 2021, pp. 3965–3973

    work page 2021

  7. [6]

    Balseiro, Y

    S. Balseiro, Y . Deng, J. Mao, V . Mirrokni, S. Zuo, Robust auction design in the auto-bidding world, Advances in Neural Information Processing Systems 34 (2021) 17777–17788

    work page 2021

  8. [7]

    S. R. Balseiro, Y . Deng, J. Mao, V . S. Mirrokni, S. Zuo, The landscape of auto-bidding auctions: Value versus utility maximization, in: Proceedings of the 22nd ACM Conference on Economics and Computation, 2021, pp. 132–133

    work page 2021

Show all 41 references
  1. [9]

    Castiglioni, A

    M. Castiglioni, A. Celli, A. Marchesi, G. Romano, N. Gatti, A unifying framework for online optimization with long-term constraints, Advances in Neural Information Processing Systems 35 (2022) 33589–33602

    2022

  2. [10]

    Golrezaei, P

    N. Golrezaei, P. Jaillet, J. C. N. Liang, V . Mirrokni, Bidding and pricing in budget and ROI constrained markets, arXiv preprint arXiv:2107.07725 8 (8.1) (2021) 3

    2021 arXiv

  3. [11]

    Balseiro, H

    S. Balseiro, H. Lu, V . Mirrokni, Dual mirror descent for online allocation problems, in: International Conference on Machine Learning, PMLR, 2020, pp. 613–628

    2020

  4. [12]

    Borgs, J

    C. Borgs, J. Chayes, N. Immorlica, K. Jain, O. Etesami, M. Mahdian, Dynamics of bid optimization in online advertisement auctions, in: Proceedings of the 16th international conference on World Wide Web, 2007, pp. 531–540

    2007

  5. [13]

    X. Chen, C. Kroer, R. Kumar, The complexity of pacing for second-price auctions, Mathematics of Operations Research (2023)

    2023

  6. [14]

    Lucier, S

    B. Lucier, S. Pattathil, A. Slivkins, M. Zhang, Autobidders with budget and ROI constraints: Efficiency, regret, and pacing dynamics, in: The Thirty Seventh Annual Conference on Learning Theory, PMLR, 2024, pp. 3642–3643

    2024

  7. [15]

    Mannor, J

    S. Mannor, J. N. Tsitsiklis, J. Y . Yu, Online learning with sample path constraints., Journal of Machine Learning Research 10 (3) (2009)

    2009

  8. [16]

    Mahdavi, T

    M. Mahdavi, T. Yang, R. Jin, Stochastic convex optimization with multiple objectives, Advances in neural information processing systems 26 (2013)

    2013

  9. [17]

    H. Yu, M. Neely, X. Wei, Online convex optimization with stochastic constraints, Advances in Neural Information Processing Systems 30 (2017)

    2017

  10. [18]

    Badanidiyuru, R

    A. Badanidiyuru, R. Kleinberg, A. Slivkins, Bandits with knapsacks, Journal of the ACM (JACM) 65 (3) (2018) 1–55

    2018

  11. [19]

    H. Yu, M. J. Neely, A low complexity algorithm with o( √ T ) regret and o(1) constraint violations for online convex optimization with long term constraints, arXiv preprint arXiv:1604.02218 (2016)

    2016 arXiv

  12. [20]

    H. Guo, X. Liu, H. Wei, L. Ying, Online convex optimization with hard constraints: Towards the best of two worlds and beyond, Advances in Neural Information Processing Systems 35 (2022) 36426–36439

    2022

  13. [21]

    Sinha, R

    A. Sinha, R. Vaze, Optimal algorithms for online convex optimization with adversarial constraints (2024). arXiv:2310.18955. URL https://arxiv.org/abs/2310.18955

    2024 arXiv

  14. [22]

    Agrawal, N

    S. Agrawal, N. R. Devanur, Fast algorithms for online stochastic convex programming, in: Proceedings of the twenty-sixth annual ACM- SIAM symposium on Discrete algorithms, SIAM, 2014, pp. 1405–1424

    2014

  15. [23]

    Rangi, M

    A. Rangi, M. Franceschetti, L. Tran-Thanh, Unifying the stochastic and the adversarial bandits with knapsack, arXiv preprint arXiv:1811.12253 (2018)

    2018 arXiv

  16. [24]

    Immorlica, K

    N. Immorlica, K. Sankararaman, R. Schapire, A. Slivkins, Adversarial bandits with knapsacks, Journal of the ACM 69 (6) (2022) 1–47

    2022

  17. [25]

    Rivera Cardoso, H

    A. Rivera Cardoso, H. Wang, H. Xu, The online saddle point problem and online convex optimization with knapsacks, Mathematics of Operations Research 50 (1) (2025) 1–39

    2025

  18. [26]

    Vaze, Online Algorithms, Cambridge University Press, 2023

    R. Vaze, Online Algorithms, Cambridge University Press, 2023

    2023

  19. [27]

    Disser, M

    Y . Disser, M. Klimm, N. Megow, S. Stiller, Packing a knapsack of unknown capacity, SIAM Journal on Discrete Mathematics 31 (3) (2017) 1477–1497

    2017

  20. [28]

    Talluri, G

    K. Talluri, G. Van Ryzin, An analysis of bid-price controls for network revenue management, Management science 44 (11-part-1) (1998) 1577–1593

    1998

  21. [29]

    L. Yang, M. H. Hajiesmaili, R. Sitaraman, E. Mallada, W. S. Wong, A. Wierman, Online inventory management with application to energy procurement in data centers, arXiv preprint arXiv:1901.04372 (2019)

    2019 arXiv

  22. [30]

    R. B. Myerson, Optimal auction design, Mathematics of operations research 6 (1) (1981) 58–73

    1981

  23. [31]

    S. C. Port, On random walks with a reflecting barrier, Transactions of the American Mathematical Society 117 (1965) 362–370

    1965

  24. [32]

    Srivastava, C

    R. Srivastava, C. E. Koksal, Basic performance limits and tradeoffs in energy-harvesting sensor nodes with finite data and energy storage, IEEE/ACM Transactions on Networking 21 (4) (2013) 1049–1062. doi:10.1109/TNET.2012.2218123

    2013

  25. [33]

    Lattimore, C

    T. Lattimore, C. Szepesv ´ari, Bandit algorithms, Cambridge University Press, 2020

    2020

  26. [34]

    Feller, An introduction to probability theory and its applications, V olumes 1-3, V ol

    W. Feller, An introduction to probability theory and its applications, V olumes 1-3, V ol. 81, John Wiley & Sons, 1991

    1991

  27. [35]

    S. Boyd, L. Vandenberghe, Convex optimization, Cambridge university press, 2004. 12 Figure 2: Input used to prove Theorem 5

    2004

  28. [36]

    The allocation functions are xθt t (of type (5)) where θt are distributed as follows

    Proof of Theorem 5 Proof: Let vt take two values {v1, v2} = {0.5, 0.9} with equal probability for all t. The allocation functions are xθt t (of type (5)) where θt are distributed as follows. Input 1: If for slot t, vt = v1, then θt ∈ {vt ± ϵ} with equal probability, where 0 < ...

  29. [37]

    Then g⋆ 3 = 0

    be the OPT’s solution to maximize (12) satisfying (13). Then g⋆ 3 = 0. Proof: Let OPT’s solution be g1 = (g1, g2, g3) to maximize (12) satisfying (13), where g3 > 0. To prove the result, we will perturb g1 to create a new solution g′ 1 that has g′ 3 = 0 and a higher valuation ...

  30. [38]

    Similarly let Input 2: vt = 1 2 ∀ t, and allocation functions are xθt t (5), where θt takes the same four values as in Input 1, A, B, C, D, but with perturbed probabilities

    Proof of Theorem 8 Proof: Consider Input 1: vt = 1 2 ∀ t, and allocation functions are xθt t (5), where θt takes four possible values A = 1 2 − u, B= 1 2 − w, C= 1 2 + m1 − δ, D= 1 2 + m1, with equal probability of 1/4 where 0 < w < u <1 2, m1 = 1 2 −u+ 1 2 −w 2 (the condition...

  31. [39]

    well-behaved

    Proof of Theorem 12 Case I µL + µR ≤ 0 Proposition 2. E{τmin} = O( √ T ) if ∆ = µL + µθ⋆ R = µL + E{1¯ v<θ · (v − θ)|θ < θ⋆} > 0 does not depend on T . Proof: From Definition 13, Margin(t) process for Ac has drift ∆ > 0 until bt < θ⋆ (and consequently the bt process has drift ...

  32. [40]

    Let the statement be false, and in particular in the optimal solution q there exists a k′ (in order) for which qk′ < 1 but qk′+1 > 0

    Proof of Lemma 18 Proof: Without loss of generality, let all vk rk be distinct. Let the statement be false, and in particular in the optimal solution q there exists a k′ (in order) for which qk′ < 1 but qk′+1 > 0. We will contradict to the optimality of q by creating a new sol...

  33. [41]

    random variables that are estimated using sample mean estimator 1 n Pn i=1 Xi, from Chernoff bound, we have P 1 n Pn i=1 Xi − E{X1} > ϵ ≤ exp−(2nϵ2)

    Proof of Theorem 19 Proof: Since all the parameters of Plight are expected values of i.i.d. random variables that are estimated using sample mean estimator 1 n Pn i=1 Xi, from Chernoff bound, we have P 1 n Pn i=1 Xi − E{X1} > ϵ ≤ exp−(2nϵ2). Thus, we get that dedicating T /2 s...

Pith tools

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