Contextual Learning for Stochastic Optimization

Anna Heuser; Thomas Kesselheim

REVIEW 3 major objections 3 minor 30 references

Contextual Learning for Stochastic Optimization

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

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

Pith's one-line read Polynomial samples from many contexts suffice to learn near-optimal policies for revenue maximization, Pandora's box, and optimal stopping.

desk verdict The conceptual framing is valuable, but the main learning bound is unsupported: the capped squared loss is not convex in the support-vector parameterization, so the central theorem collapses. read the letter →

arxiv 2505.16829 v1 pith:EZO6MTN6 submitted 2025-05-22 cs.LG cs.DScs.GT

Anna Heuser , Thomas Kesselheim This is my paper · ORCID

classification cs.LGcs.DScs.GT

keywords contextualvaluedistributionscappedsquaredlossLévydistancesamplecomplexitystochasticoptimizationrevenuemaximizationPandora'sboxoptimalstopping

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 introduces a learning problem in which each context $x$ carries a real-valued reward distribution, and the learner only sees samples $(x, f(v,x))$ where $v$ is an unobserved weight vector. It proposes a capped squared loss that compares, over a fine grid of caps $c$, the predicted capped expectation of a learned distribution with the capped value observed in the sample. Minimizing this loss with convex optimization yields a distribution that is close to the true reward distribution in Lévy distance. Because revenue maximization, Pandora's box, and optimal stopping are strongly monotone and stable under small Lévy perturbations, this distributional closeness transfers to near-optimal policies. The result is the first general polynomial sample-complexity bound for these contextual stochastic optimization problems.

What carries the argument

The central object is the capped squared loss $L_x(V') = \mathbb{E}_{v^*\sim V^*} \left[ \sum_{c \in C_\epsilon} \left( \mathbb{E}_{v'\sim V'}[\max\{c, f(v',x)\}] - \max\{c, f(v^*,x)\} \right)^2 \right]$, where $C_\epsilon$ is an $\epsilon$-grid on $[0, c_{\max}]$. The loss is designed to be convex in the support vectors of a learned uniform distribution, so standard convex-learning bounds apply and the regularized empirical-risk minimizer over $k$ support points is tractable. The load-bearing identity (Lemma 5, via Lemma 6) shows that $L_x(V') - L_x(V^*)$ equals the sum over the grid of squared differences of capped expectations; hence small loss implies a uniform bound on all capped expectations, which in turn bounds the Lévy distance of the induced reward distributions. The other load-bearing pieces are the structural properties of the downstream problems — strong monotonicity and $\gamma$-stability — which convert small Lévy distance into near-optimal policies, and, for Pandora's Box and Optimal Stopping, the direct use of capped expectations to compute fair caps and thresholds.

What would settle it

Compute the capped squared loss for $f(v,x)=v^2$, $y=0.5$, $C_\epsilon=\{0\}$, on the uniform distribution over $(v_1,v_2)$: the loss is $\left(\frac{v_1^2+v_2^2}{2}-0.5\right)^2$. Along the line $v_1=v_2=t$ the second derivative is $12t^2-2$, which is negative for $t<1/\sqrt{6}$; therefore the loss is not convex, contradicting the lemma used to justify the convex-learning step.

Watch

Extended reading notes

Core claim

The paper's central claim is that contextual stochastic optimization is learnable with polynomial sample complexity: for any strongly monotone and $\gamma$-stable problem on $n$ unknown contextual value distributions, $O(d \xi^2 c_{\max}^4 / (\epsilon^{16} \delta^2))$ samples from each distribution suffice to choose a policy whose expected reward is within $2\gamma\epsilon$ of optimal with probability at least $1-n\delta$. The engine is a careful translation between a convex surrogate objective — the capped squared loss — and the Lévy metric on reward distributions (a measure of closeness of cumulative distribution functions). The paper further shows that, when the optimal policy only needs capped expectations rather than full distributions, the same argument can be run directly on those expectations, improving the exponent of $\epsilon$ from 16 to 8 for Pandora's Box and Optimal Stopping. Thus, even though a test context will almost surely differ from every sampled context, the learner can still act near-optimally.

Load-bearing premise

The argument relies on the claim that the capped squared loss is convex in the support vectors of the learned distribution, so that the regularized empirical-risk minimizer can be found efficiently by convex optimization.

Editorial extensions

If this is right

For any strongly monotone and $\gamma$-stable problem, $O(d \xi^2 c_{\max}^4 / (\epsilon^{16} \delta^2))$ samples from each distribution yield a policy with expected reward within $2\gamma\epsilon$ of the optimum, with probability at least $1-n\delta$.
For Pandora's Box and Optimal Stopping, the direct capped-expectation analysis improves the bound to $O(d \xi^2 c_{\max}^4 / (\epsilon^8 \delta^2))$, a factor $\epsilon^8$ better.
The learned distribution $V'$ is $\epsilon$-close to $V^*$ in Lévy distance, and hence also within $O(\epsilon)$ in Wasserstein distance, so a coupling between the true and learned reward distributions exists.
The empirical-risk minimizer can be found efficiently because the search can be restricted to uniform distributions over a polynomially bounded number of support vectors.

Reading between the lines

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

A natural test is to replace the squared loss by a Huber-style loss; if the capped-expectation error bounds survive, the framework would extend to settings where the squared loss is non-convex.
The generic $\epsilon^{16}$ dependence suggests the Lévy route is lossy; one could seek a direct capped-expectation analysis for all strongly monotone and stable problems, which would likely reduce the exponent to $\epsilon^8$ uniformly.
The framework should transfer to other stable optimization problems (e.g., matroid prophet inequalities or sequential posted pricing) as long as they satisfy the monotonicity and stability conditions; verifying stability for these would expand the menu of applications.

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.

Desk Editor's Note

read the letter

Frankly, the headline is that the central learning theorem is not proven. The stress-test counterexample is correct: for d=1, f(v,x)=v^2, c=0, y=0.5, the loss ((v1^2+v2^2)/2 − 0.5)^2 has a negative-definite Hessian at (0,0). So the capped squared loss is not convex in the concatenated support-vector parameterization, and Theorem 17 from Shalev-Shwartz et al. cannot be applied. That breaks Lemma 4 and therefore Theorem 1 and everything downstream. The "by design convex" assertion in Sections 3 and 4.2 is simply false.

The Markov step in Theorem 1 is also hand-wavy, but that one is probably repairable with a tighter choice of constants; the convexity failure is not repairable within the proposed parameterization. If you change the parameterization (e.g., mixture weights over a fixed grid, or a different surrogate), the arguments might go through, but as written the sample-complexity claims are unsupported.

That said, the paper deserves credit for the framework. The contextual value distribution model is a natural generalization of problem-specific contextual models, and the idea of using capped expectations as a surrogate to control Lévy distance is clean. Lemma 5 and Theorem 7, which convert a loss bound into a bound on capped expectations and then into a Lévy guarantee, are logically sound given the loss bound. The applications sections are also thoughtful: the stability arguments for Pandora's Box and Optimal Stopping, and the improved bounds via capped expectations, look plausible and would be valuable if the learning step held up. The related work is thorough and fair, and the self-citation is to an independent published result.

Bottom line: this is a promising research program but not a finished paper. The main results are not established. A serious referee should engage with it—the framework may well be salvageable—but the decision on the current version should be reject. It would be a good reading-group paper precisely because the flaw is instructive.

Referee Report

3 major / 3 minor

Summary. The paper introduces a contextual learning framework for stochastic optimization. A learner observes samples (x, f(v, x)) where v is drawn from an unknown weight distribution V^* and x from a context distribution X, with v hidden. The goal is to learn, for each context, a reward distribution close to the true induced distribution in Lévy distance. The paper defines a capped squared loss over a grid C_epsilon of caps, claims that this loss is convex and Lipschitz so that convex ERM can learn a distribution with small true loss, then shows that small loss implies small difference in all capped expectations, which in turn implies small Lévy distance. These results are then applied to strongly monotone and gamma-stable stochastic optimization problems, yielding polynomial sample-complexity bounds for Single-item Revenue Maximization, Pandora's Box, and Optimal Stopping, with improved O(1/epsilon^8) bounds for the latter two via capped expectations.

Significance. If the main theorems were correct, this would be a valuable unified framework: it would connect a convex surrogate loss to Lévy distance and thereby give sample-complexity guarantees for a broad class of stochastic optimization problems without problem-specific analyses. The paper is self-contained, states its assumptions clearly, and uses established results as black boxes. The observation in Lemma 6 that the difference of true losses equals a sum of squared capped-expectation gaps is elegant, and the capped-expectation route to Pandora's Box is plausible. However, the entire sample-complexity chain rests on a false convexity assertion in the parameterization used for the ERM step. Because that assertion is load-bearing for Lemma 4 and Theorem 1, the central claims of the paper are not established. The remaining issues are repairable in principle, but the convexity failure is not a local fix within the proposed framework.

major comments (3)

[Section 3 / Section 4.2 / Lemma 4 / Theorem 1] The claim that the capped squared loss is convex in the support-vector parameterization is false. For d=1, k=2, f(v,x)=v^2, sample value y=1/2, and c=0 in C_epsilon, the per-sample loss contains the term ((v_1^2+v_2^2)/2 - 1/2)^2. Its Hessian at (0,0) is -I, and along v_1=v_2=t the second derivative of (t^2-1/2)^2 is 12t^2-2, which is negative near t=0. The capped terms for c>0 are constant in a neighborhood of the origin and cannot restore convexity. Since Theorem 17 in Appendix B requires the per-sample loss to be convex in the hypothesis, the application of Shalev-Shwartz et al. (2010) in Lemma 4 is invalid. Consequently Theorem 1, Corollaries 1 and 2, and Theorem 8 are unsupported.
[Proof of Theorem 1] The Markov step is not justified as written. Lemma 4 gives a bound on E_S[L(V')], the expectation over the sample set S, but the conclusion is a high-probability statement about L_x(V') for a fresh context x. To make this step valid, one must apply Markov to the joint expectation over (S,x), and the approximation error and learning error must be allocated so that the total expectation gap is O(epsilon delta). As written, the quantifier handling is skipped; this is likely repairable, but it is a gap in the proof.
[Appendix A, proof of Lemma 2] The positive-probability argument uses a union bound over |C_epsilon| * |X_{gamma,d}| events, but Hoeffding's inequality as quoted has a factor 2. With the stated sample size n = 2 c_max^3/epsilon^2 log(2(2d c_max)^d/epsilon^{d+1}) and gamma = epsilon/(2 sqrt(c_max)), the Hoeffding bound for a single (c,x) event is 2/M, not 1/M, where M = |C_epsilon| |X_{gamma,d}|. When c_max = 1 this makes the union bound only <= 1, which does not establish the existence of the desired sample set. The lemma can probably be repaired by increasing the logarithmic factor by a constant, but the proof as written is incomplete.

minor comments (3)

[Lemma 3] The displayed derivative of the capped squared loss appears to use the factor (2/k) sum max(c,f(v_i,x)) - y, whereas the derivative of (average - y)^2 is 2(average - y); with the stated bound the Lipschitz constant 2 c_max^2/epsilon sqrt(k) xi does not follow. A direct computation gives a bound of order c_max^2 xi/(epsilon sqrt(k)), which is the form needed for the cancellation in Lemma 4.
[Lemma 15] The statement 'R_D(pi^*(D')) >= R_D(pi^*(D')) - 2n epsilon' is trivially true. From the proof, the intended conclusion appears to be R_D(pi^*(D')) >= R_D(pi^*(D)) - 2n epsilon, which is the bound needed for the subsequent sample-complexity claim.
[Section 7.3, Lemma 11 proof] The notation 'tilde D_i(r_i)' is described as the distribution of pairs given by tilde D_i conditioned on r_i, but conditioning on r_i already fixes the first marginal; the subsequent use suggests it should be the conditional distribution of r'_i given r_i.

Circularity Check

0 steps flagged · score 2.0 of 10

No load-bearing circularity: the capped-expectation-to-Levy chain is a standard ERM-plus-approximation argument, and the only overlapping-author citation is an independent published stability result not needed by the improved bounds.

full rationale

The derivation chain is self-contained. The paper defines a capped squared loss, invokes the Shalev-Shwartz et al. (2010) convex-learning guarantee to obtain a bounded-support empirical minimizer with small true loss, converts small true loss into small capped-expectation error via the algebraic identity in Lemma 6 (Lemma 5), then converts capped-expectation closeness into Levy closeness (Theorem 7), and finally into policy-value approximation through strong monotonicity and stability (Theorem 8). No step fits a parameter to the target quantity and then re-predicts it; Theorem 1 is a standard generalization bound, not a fitted-input-called-prediction. The sole overlapping-author citation is Dutting and Kesselheim (2019), used in Section 7.4 as one route to the O(d/(epsilon^16 delta^2)) Optimal Stopping bound; that result is an independent peer-reviewed stability statement, and the improved O(d/(epsilon^8 delta^2)) Optimal Stopping bound is proved in Lemma 15 without it. Hence the self-citation is minor and not load-bearing. The paper does contain a serious non-circular technical flaw: it asserts the capped squared loss is 'by design convex' (Sections 3 and 4.2), but in the concatenated support-vector parameterization the loss need not be convex; for d=1, f(v,x)=v^2, C_epsilon={0}, and y=0.5, the per-sample loss ((v_1^2+v_2^2)/2 - 0.5)^2 has a negative-definite Hessian at (0,0). Thus Lemma 4 and Theorem 1 are not established by the cited convex-learning theorem. That is a correctness problem, not circularity, and does not raise the circularity score beyond the minor-self-citation level.

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

The central claim rests on four classes of assumptions: standard probability and convex learning results, the domain model of convex Lipschitz reward functions, and two ad hoc premises specific to this paper: the convexity of the capped squared loss in the chosen parameterization (false) and the validity of a Markov step converting expected loss into a per-context high-probability bound (unjustified). The loss itself introduces no fitted constants; ε is an accuracy parameter.

assumptions (5)

ad hoc to paper The capped squared loss is convex in the learned distribution and the hypothesis space V_k is closed and convex.
Assumed in Section 3 and 4.2 to apply convex learning (Theorem 17 from Shalev-Shwartz et al. 2010). False for the uniform-k-support-vector parameterization: with f(v,x)=v^2, y=0.5, C_ε={0}, the loss ((v_1^2+v_2^2)/2 - 0.5)^2 is non-convex in (v_1,v_2).
ad hoc to paper A bound on E_S[L(V')] over samples and contexts implies a high-probability bound on L_x(V') for a single drawn context x.
Used in the proof of Theorem 1. The Markov step is invalid because the expectation in Lemma 4 is over samples and contexts, not over samples for a fixed context.
standard math Standard results from probability and convex learning theory (Hoeffding's inequality, the regularized ERM guarantee of Shalev-Shwartz et al. 2010) are correct.
Invoked in Section A and B.
domain assumption The reward function f is convex and Lipschitz in both arguments, with range [0, c_max], and contexts and weights are drawn i.i.d.
Problem setup in Section 2.
domain assumption The cited stability and strong-monotonicity results (Guo et al. 2021, Dütting and Kesselheim 2019, Brustle et al. 2020, Atsidakou et al. 2024) apply to the contextual instances.
Used in Section 7 to transfer distribution closeness to policy near-optimality.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Contextual Learning for Stochastic Optimization." pith.science (2026). https://pith.science/paper/EZO6MTN6

@misc{pith2026250516829,
  author       = {Pith},
  title        = {Pith review of: Contextual Learning for Stochastic Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EZO6MTN6}},
  note         = {Machine review of arXiv:2505.16829}
}

abstract

Motivated by stochastic optimization, we introduce the problem of learning from samples of contextual value distributions. A contextual value distribution can be understood as a family of real-valued distributions, where each sample consists of a context $x$ and a random variable drawn from the corresponding real-valued distribution $D_x$. By minimizing a convex surrogate loss, we learn an empirical distribution $D'_x$ for each context, ensuring a small L\'evy distance to $D_x$. We apply this result to obtain the sample complexity bounds for the learning of an $\epsilon$-optimal policy for stochastic optimization problems defined on an unknown contextual value distribution. The sample complexity is shown to be polynomial for the general case of strongly monotone and stable optimization problems, including Single-item Revenue Maximization, Pandora's Box and Optimal Stopping.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 26 canonical work pages

[1]

Taming the monster: A fast and simple algorithm for contextual bandits

Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1638--1646. PMLR, 2014

work page 2014
[2]

Semi-bandit learning for monotone stochastic optimization

Arpit Agarwal, Rohan Ghuge, and Viswanath Nagarajan. Semi-bandit learning for monotone stochastic optimization. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024 , pages 1260--1274. IEEE , 2024

work page 2024
[3]

Contextual pandora’s box

Alexia Atsidakou, Constantine Caramanis, Evangelia Gergatsouli, Orestis Papadigenopoulos, and Christos Tzamos. Contextual pandora’s box. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10944--10952, 2024

work page 2024
[4]

Multi-item mechanisms without item-independence: Learnability via robustness

Johannes Brustle, Yang Cai, and Constantinos Daskalakis. Multi-item mechanisms without item-independence: Learnability via robustness. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 715--761, 2020

work page 2020
[5]

Nonparametric pricing analytics with customer covariates

Ningyuan Chen and Guillermo Gallego. Nonparametric pricing analytics with customer covariates. Operations Research, 69 0 (3): 0 974--984, 2021

work page 2021
[6]

Contextual bandits with linear payoff functions

Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 208--214. PMLR, 2011

work page 2011
[7]

Cohen, Ilan Lobel, and Renato Paes Leme

Maxime C. Cohen, Ilan Lobel, and Renato Paes Leme. Feature-based dynamic pricing. Management Science, 66 0 (11): 0 4921--4943, 2020

work page 2020
[8]

The sample complexity of revenue maximization

Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 243--252, 2014

work page 2014

Show all 30 references

[9]

Prophet inequalities for independent and identically distributed random variables from an unknown distribution

Jose Correa, Paul D \"u tting, Felix Fischer, and Kevin Schewior. Prophet inequalities for independent and identically distributed random variables from an unknown distribution. Mathematics of Operations Research, 47 0 (2): 0 1287--1309, 2022

2022
[10]

The sample complexity of auctions with side information

Nikhil R Devanur, Zhiyi Huang, and Christos-Alexandros Psomas. The sample complexity of auctions with side information. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 426--439, 2016

2016
[11]

Efficient optimal leanring for contextual bandits

Miroslav Dud\'ik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal leanring for contextual bandits. 27th Conf. on Uncertainty in Artificial Intelligence (UAI), 2011

2011
[12]

Posted pricing and prophet inequalities with inaccurate priors

Paul D \" u tting and Thomas Kesselheim. Posted pricing and prophet inequalities with inaccurate priors. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019 , pages 111--129. ACM , 2019

2019
[13]

Practical contextual bandits with regression oracles

Dylan Foster, Alekh Agarwal, Miroslav Dud \' k, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pages 1539--1548. PMLR, 2018

2018
[14]

Bandit algorithms for prophet inequality and pandora's box

Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang. Bandit algorithms for prophet inequality and pandora's box. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 462--500. SIAM, 2024

2024
[15]

Online learning for min sum set cover and pandora’s box

Evangelia Gergatsouli and Christos Tzamos. Online learning for min sum set cover and pandora’s box. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 7382--7403, 2022

2022
[16]

On choosing and bounding probability metrics

Alison L Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International statistical review, 70 0 (3): 0 419--435, 2002

2002
[17]

Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora’s problem

Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang. Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora’s problem. In Conference on Learning Theory, pages 2248--2288. PMLR, 2021

2021
[18]

Probability inequalities for sums of bounded random variables

Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58 0 (301): 0 13--30, 1963

1963
[19]

Dynamic pricing in high-dimensions

Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing in high-dimensions. Journal of Machine Learning Research, 20 0 (9): 0 1--49, 2019

2019
[20]

Sample complexity of posted pricing for a single item

Billy Jin, Thomas Kesselheim, Will Ma, and Sahil Singla. Sample complexity of posted pricing for a single item. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=EK1tyHcb3W

2024
[21]

The epoch-greedy algorithm for multi-armed bandits with side information

John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007

2007
[22]

Distribution-free contextual dynamic pricing

Yiyun Luo, Will Wei Sun, and Yufeng Liu. Distribution-free contextual dynamic pricing. Mathematics of Operations Research, 49 0 (1): 0 599--618, 2024

2024
[23]

Ironing in the dark

Tim Roughgarden and Okke Schrijvers. Ironing in the dark. arXiv preprint arXiv:1511.06918, 2015

2015 arXiv
[24]

Learnability, stability and uniform convergence

Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11 0 (90): 0 2635--2670, 2010. URL http://jmlr.org/papers/v11/shalev-shwartz10a.html

2010
[25]

Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability

David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 47 0 (3): 0 1904--1931, 2022

1904
[26]

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

Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan J Foster. Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression. In The Thirty Sixth Annual Conference on Learning Theory, pages 4633--4656. PMLR, 2023

2023
[27]

Improved algorithms for contextual dynamic pricing

Matilde Tullii, Solenne Gaucher, Nadav Merlis, and Vianney Perchet. Improved algorithms for contextual dynamic pricing. arXiv preprint arXiv:2406.11316, 2024

2024 arXiv
[28]

The nature of statistical learning theory

Vladimir Vapnik. The nature of statistical learning theory. Springer, 2013

2013
[29]

Weitzman

Martin L. Weitzman. Optimal search for the best alternative. Econometrica, 47 0 (3): 0 641--654, 1979

1979
[30]

Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise

Jianyu Xu and Yu-Xiang Wang. Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise. In International Conference on Artificial Intelligence and Statistics, pages 9643--9662. PMLR, 2022

2022

Pith tools

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

[1] [1]

Taming the monster: A fast and simple algorithm for contextual bandits

Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1638--1646. PMLR, 2014

work page 2014

[2] [2]

Semi-bandit learning for monotone stochastic optimization

Arpit Agarwal, Rohan Ghuge, and Viswanath Nagarajan. Semi-bandit learning for monotone stochastic optimization. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024 , pages 1260--1274. IEEE , 2024

work page 2024

[3] [3]

Contextual pandora’s box

Alexia Atsidakou, Constantine Caramanis, Evangelia Gergatsouli, Orestis Papadigenopoulos, and Christos Tzamos. Contextual pandora’s box. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10944--10952, 2024

work page 2024

[4] [4]

Multi-item mechanisms without item-independence: Learnability via robustness

Johannes Brustle, Yang Cai, and Constantinos Daskalakis. Multi-item mechanisms without item-independence: Learnability via robustness. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 715--761, 2020

work page 2020

[5] [5]

Nonparametric pricing analytics with customer covariates

Ningyuan Chen and Guillermo Gallego. Nonparametric pricing analytics with customer covariates. Operations Research, 69 0 (3): 0 974--984, 2021

work page 2021

[6] [6]

Contextual bandits with linear payoff functions

Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 208--214. PMLR, 2011

work page 2011

[7] [7]

Cohen, Ilan Lobel, and Renato Paes Leme

Maxime C. Cohen, Ilan Lobel, and Renato Paes Leme. Feature-based dynamic pricing. Management Science, 66 0 (11): 0 4921--4943, 2020

work page 2020

[8] [8]

The sample complexity of revenue maximization

Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 243--252, 2014

work page 2014