betaFeedback

WorksComputer Science

Budgeted Bayesian Bandits for Future Utilization

Abstract

The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against a primal linear programming relaxation for a more general model. We show that the analyses of both algorithms are tight, even when their relaxations are asymptotically exact. We provide a different efficient algorithm that achieves a 0.43 approximation. We then provide an efficient algorithm whose guarantee approaches 1-e^{-1} approx 0.63 for bounded exchangeable reward observations in a non-vanishing regime, which is asymptotically tight against natural linear programming relaxations. The technique also gives certificates for stopping sequential model evaluation.

Introduction

Sequential experimental design was developed in the context of industrial quality control with roots in Wald’s sequential analysis [59]. Box and Wilson (1951) introduced response surface methodology, in which each round of experiments chooses factor levels based on the results so far. Parallel to that optimization-focused approach, sequential data monitoring and adaptive sampling ideas subsequently became central to the clinical trial literature [2, 3]. More recently, software-generated alternatives have brought sequential design back to the fore: there are often many candidate models and only a limited budget for evaluating them [48 b]. Related problems of measurement and learning arise in fields such as network monitoring [38, 64] and consumer studies [13, 7].

Consider nn independent, but not necessarily identical, rested Bayesian arms with known priors and a horizon TT. A policy π\pi plays one arm at each step, observes its outcome, and updates the posteriors. At the end of the horizon, the policy selects an arm with the largest posterior utility. For posterior-mean as the utility, let θi\theta_i denote the latent mean reward of arm ii, and let FTπ\mathcal{F}^{\pi}_T denote the information available after exploration. Define the value of the optimum policy OPTT\mathrm{OPT}_T as follows

VT(π)=E[max⁡iE[θi∣FTπ]],OPTT=sup⁡πVT(π),V_T(\pi)=\mathbb{E}\left[\max_i\mathbb{E}[\theta_i\mid\mathcal{F}^{\pi}_T]\right], \qquad\mathrm{OPT}_T=\sup_{\pi}V_T(\pi),

where the supremum is over policies satisfying the exploration budget. Rewards obtained during exploration do not contribute to this objective and standard cumulative regret is a very different optimization. Simple regret [12, 4] compares the selected arm with the best arm under the true means [11 Section 7.2]; averaged over the prior it is E[max⁡iθi]−VT(ALG)\mathbb{E}[\max_i\theta_i]-V_T(\mathrm{ALG}), which splits into E[max⁡iθi]−OPTT\mathbb{E}[\max_i\theta_i]-\mathrm{OPT}_T, the least regret achievable with the budget, and OPTT−VT(ALG)\mathrm{OPT}_T-V_T(\mathrm{ALG}), the loss from the chosen policy.

Consider n=2Tn=2T independent, identically distributed arms, each with θi=1\theta_i=1 with probability 1/n1/n and θi=0\theta_i=0 otherwise, where one play reveals θi\theta_i. This is a needle-in-a-haystack example with non-vanishing expected reward where the perfect-information value tends to 1−e−11-e^{-1}, whereas OPTT=1−(1−1/n)T+1→1−e−1/2\mathrm{OPT}_T=1-(1-1/n)^{T+1}\to1-e^{-1/2}. The extra term in the exponent accounts for selecting an uninspected arm after TT unsuccessful inspections. The budget thus allows substantial value, but even the optimal policy has limiting simple regret e−1/2−e−1>0e^{-1/2}-e^{-1}>0. If instead T=o(n)T=o(n) with the same success probability 1/n1/n, OPTT→0\mathrm{OPT}_T\to0. The optimal policy and a policy inspecting only one arm then have the same limiting simple regret 1−e−11-e^{-1}, although the latter obtains only an O(1/T)O(1/T) fraction of OPTT\mathrm{OPT}_T. Measuring policies against OPTT\mathrm{OPT}_T distinguishes policy quality from this unavoidable informational loss.

The Gittins index [61, 24] is optimal for discounted cumulative reward, but not for a fixed exploration budget followed by a single terminal choice. The problem can be formulated as a Markov decision process and solved by dynamic programming [6, 9] over the joint product state space of the arms. This computation is exponential in general, and no exact algorithm is known that runs in time polynomial in the sum of the single-arm state spaces. Madani et al. (2004a) show that the problem is NP-hard when plays of different arms have different costs, and leave the unit-cost case, studied here, open. We focus on efficient algorithms guaranteeing VT(ALG)≥f⋅OPTTV_T(\mathrm{ALG}) \ge f \cdot\mathrm{OPT}_T, where ALG\mathrm{ALG} denotes the algorithm under consideration (by convention, for maximization problems, the factor f≤1f \le1, larger is better). Our upper bounds on OPTT\mathrm{OPT}_T come from linear programming relaxations with optimal value LP≥OPTT\mathrm{LP} \ge\mathrm{OPT}_T; the ratio LP/OPTT\mathrm{LP}/\mathrm{OPT}_T is the integrality gap.

The budgeted problem was posed by Madani et al. (2004b), and Guha and Munagala (2007, 2008) gave the first constant-factor approximations through LP relaxations. In their consolidated treatment, Guha and Munagala (2013, Section 7) (abbreviated GM13 henceforth) obtain a 1/3 approximation by balancing a Lagrangian bound and executing the resulting policies. Ma (2018, Section 1.3) gives an LP-based 4/27 guarantee for a more general Markovian model that does not require exchangeability. We show that these guarantees are tight for the corresponding algorithms, even when their relaxations are asymptotically exact (Propositions 2.4 and 2.6). We then provide a better algorithm achieving a factor $(1-e^{-2})/2 \approx 0.43 ({xref}Section 2.1`).

Our main technical tool is selection-preserving truncation for Bayesian arms with exchangeable observations in [0,1][0,1] (§ 4). The local policies of an optimal LP solution can be truncated to depth k=O(log⁡(n/(ϵLP))/(ϵ2LP))k = O(\log(n/(\epsilon\mathrm{LP}))/(\epsilon^2\mathrm{LP})), with no explicit dependence on TT, while preserving each arm’s selection probability, not increasing its expected play count, and losing at most 4ϵLP4\epsilon\mathrm{LP} reward in aggregate (Corollary 4.3). The short-policy result of § 3 then incurs little additional loss beyond the selection-only factor 1−e−11-e^{-1}. Together these give a (1−e−1−o(1))(1-e^{-1}-o(1)) approximation against LP when T⋅LP≫log⁡(n/LP)T \cdot\mathrm{LP} \gg\log(n/\mathrm{LP}), and establish the tight asymptotic integrality gap 1/(1−e−1)1/(1-e^{-1}) (Corollary 4.5). We call this the non-vanishing regime: for n≥2n \ge2, u=log⁡(n/LP)/(T⋅LP)→0u = \log(n/\mathrm{LP})/(T \cdot\mathrm{LP}) \to0, so the LP value does not vanish on the scale log⁡(n/LP)/T\log(n/\mathrm{LP})/T. The regime allows LP→0\mathrm{LP} \to0 and n>Tn > T. The condition implies that the truncation depth kk is o(T)o(T), so the scheduling loss vanishes with the parameters set in Corollary 4.5. Outside it, two guarantees remain: Theorem 2.1 gives 0.43 on every instance, and for one-play revelations Theorem 3.3 with k=1k=1 gives (1−e−1−O(log⁡T/T))LP(1-e^{-1}-O(\sqrt{\log T/T}))\mathrm{LP} even when OPT→0\mathrm{OPT} \to0, as in the needle family with T=o(n)T=o(n). Over all exchangeable instances, the worst-case integrality gap of LP is therefore at least 1/(1−e−1)1/(1-e^{-1}) and at most 2/(1−e−2)2/(1-e^{-2}); we do not know whether instances outside the regime can exceed 1/(1−e−1)1/(1-e^{-1}).

Section 5 uses the dual of the truncated LP as a computable, instance-specific upper bound on the value of further evaluation. This gives a stopping rule with a simple-regret guarantee, and variants for switching, setup and movement budgets. Section 6 treats terminal utilities, satisficing, and joint selection and prediction objectives.

Related work

Budgeted learning and model selection. Budgeted learning of naive-Bayes classifiers purchases attribute values of labelled examples under a hard budget [46]. Proposals for this problem include Biased Robin and single-feature lookahead [46, 40], reinforcement learning [41], and purchase rules derived from bandit algorithms [17, 18]. Without a hard budget, the related problem is active feature-value acquisition [54]. A bounded active classifier also pays for attributes used at prediction time [28]; its budgeted learning therefore ends with a subset choice [39]. Modern model selection likewise allocates limited evaluation to many candidate configurations [44], or evaluates pre-trained classifiers under a labelling budget [42]. The latter considers dependence outside our independent-arm model.

Optimization formulations. § 2.4 separates selectable martingale payoffs from the late payoffs in general Markov models [34] (Ma 2018); the latter require time-indexed relaxations. Goel et al. (2009) proposed a ratio index for budgeted learning.1 When one inspection resolves an alternative and inspections are priced, Pandora’s box optimizes expected selected value minus inspection costs [60]. LP relaxations of adaptive policies are also used for stochastic knapsack [15] and stochastic probing [27, 33].

Pure exploration, selection, and stopping. Bayesian ranking and selection uses the expected largest posterior mean after a measurement budget; the knowledge gradient chooses each measurement by its one-step value (Frazier et al., 2008). Sampling and stopping are already coupled in this literature. Frazier and Powell [22] jointly design them with a myopic measurement-cost objective. Eckman and Henderson [19] give computationally efficient checks of posterior selection probability and expected opportunity cost. Hay et al. [35] analyze the value of further sampling, including perfect-information bounds and finite sampling bounds for one Bernoulli arm with measurement costs. In Bayesian optimization, Ishibashi et al. [37] use changes in an expected simple-regret criterion, Wilson [62] certifies posterior probability of near-optimality, and Xie et al. [63] study cost-adjusted simple regret and expected-budget guarantees.

Resource constraints and switching. Bandits with knapsacks add resource budgets to online reward maximization [5]. Their LP bounds and primal-dual resource prices provide an optimization perspective on learning under limited supply; Agrawal and Devanur [1] extend the model to concave rewards and convex constraints. These objectives value outcomes during learning, whereas here observations precede a terminal choice. In pure exploration, Li and Cheung [45] study best-arm identification with resource consumption on each pull, distinguishing deterministic and stochastic consumption. Resource use can also depend on the order of evaluation: Hong and Nelson [36] explicitly trade sampling against switching in indifference-zone selection, and Mwai et al. [50] constrain the expected switching rate in fixed-confidence exploration. For cumulative regret, Simchi-Levi and Xu [57] study hard switching budgets and characterize phase transitions in the minimax rate; Koren et al. [43] study adversarial losses with metric movement penalties.

Policies and relaxations

There are nn independent rested arms. Arm ii has root ρi\rho_i, states u∈Siu \in\mathcal{S}_i, and transitions u→vu \to v with probabilities puvp_{uv}. Each transition consumes one play. Local depth is included in the state and is at most TT. The arm can be selected at any state for a known nonnegative payoff rur_u. Until Section 2.4, we assume

ru≥∑v:u→vpuvrv.(1)r_u \ge\sum_{v:u\to v} p_{uv}r_v. \tag*{(1)}

Equality is the martingale case. Only the terminal selection contributes to the objective. A global policy uses at most TT plays and selects at most one arm. For the Bayesian model used in Section 4, each arm has a fixed latent reward distribution on [0,1][0,1], drawn independently from its prior. Conditional on this distribution, observations are iid and immediately available. Its mean is θi\theta_i, and ru=E[θi∣u]r_u = \mathbb{E}[\theta_i \mid u]. Thus observations are exchangeable, and (1) holds with equality.

Local policies. A single-arm policy PP terminates by selecting or quitting, and uses at most TT plays. Following GM13, let R~(P)\widetilde{R}(P) be its expected selected payoff, I(P)I(P) its selection probability, and W(P)W(P) its expected play count. For a fixed policy PiP_i write

Ri=R~(Pi),qi=I(Pi),wi=W(Pi).R_i = \widetilde{R}(P_i), \quad q_i = I(P_i), \quad w_i = W(P_i).

For each PiP_i, consider its complete local execution from its root to its own terminal decision, without the shared play budget. Let τi\tau_i be its random duration, IiI_i its selection indicator, and Yi=ruiIiY_i = r_{u_i} I_i its selected payoff, with Yi=0Y_i = 0 if it quits. Hence Ri=EYiR_i = \mathbb{E}Y_i, qi=EIiq_i = \mathbb{E}I_i, and wi=Eτiw_i = \mathbb{E}\tau_i. Use independent transitions and local randomization across arms, so (τi,Ii,Yi)(\tau_i, I_i, Y_i) are independent across ii. To analyze a global execution, use these same outcomes and local decisions whenever it runs PiP_i. The variables above describe the complete local execution, even if the global execution never starts PiP_i or interrupts it before its terminal decision. The null policy quits immediately without playing or selecting; its duration, selection indicator, and selected payoff are all zero.

Two constraints. The relaxations are standard:

LP=max⁡{Pi}{∑iRi:∑iqi≤1, ∑iwi≤T}.(2)\mathrm{LP}=\max_{\{\mathcal{P}_i\}}\left\{\sum_i R_i:\sum_i q_i\le1,\ \sum_i w_i\le T\right\}. \tag*{(2)}
LPBud=max⁡{Pi}{∑iRi:∑i(qi+wi/T)≤2}.(3)\mathrm{LPBud}=\max_{\{\mathcal{P}_i\}}\left\{\sum_i R_i:\sum_i(q_i+w_i/T)\le2\right\}. \tag*{(3)}

The LPBud formulation was introduced in Guha and Munagala [32]. Marginalizing a feasible global policy over all other arms gives feasible local flows for (2). Adding the two constraints gives

OPT≤LP≤LPBud.(4)\mathrm{OPT}\le\mathrm{LP}\le\mathrm{LPBud}. \tag*{(4)}

For completeness, the local flow variables are reach zuz_u, play xux_u, and selection sus_u, satisfying

zρi=1,zv=∑u:u→vpuvxu,xu+su≤zu,zu,xu,su≥0.(5)z_{\rho_i}=1,\qquad z_v=\sum_{u:u\to v}p_{uv}x_u,\qquad x_u+s_u\le z_u,\qquad z_u,x_u,s_u\ge0. \tag*{(5)}

References

  1. [1]Shipra Agrawal and Nikhil R. Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the 15th ACM Conference on Economics and Computation, pages 989–1006, 2014. doi: 10.1145/2600057.2602844. URL https://arxiv.org/abs/1402.5758.
  2. [2]F. J. Anscombe. Sequential medical trials. Journal of the American Statistical Association, 58(302): 365–383, 1963. URL https://www.jstor.org/stable/2283272.DOI
  3. [3]Peter Armitage, C. K. McPherson, and B. C. Rowe. Repeated significance tests on accumulating data. Journal of the Royal Statistical Society: Series A (General), 132(2):235–244, 1969. doi: 10.2307/2343787.DOI
  4. [4]Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In Proceedings of the 23rd Conference on Learning Theory (COLT), pages 41–53, 2010.
  5. [5]Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013. doi: 10.1109/FOCS.2013.30. URL https://arxiv.org/abs/1305.2545.
  6. [6]Richard Bellman. The theory of dynamic programming. Bulletin of the American Mathematical Society, 60(6):503–515, 1954. doi: 10.1090/S0002-9904-1954-09848-8.DOI
  7. [7]Dimitris Bertsimas and Adam J. Mersereau. A learning approach for interactive marketing to a customer segment. Operations Research, 55(6):1120–1135, 2007. doi: 10.1287/opre.1070.0427.DOI
  8. [8]David Blackwell. Equivalent comparisons of experiments. The Annals of Mathematical Statistics, 24(2): 265–272, 1953. doi: 10.1214/aoms/1177729032.DOI
  9. [9]David Blackwell. Discounted dynamic programming. The Annals of Mathematical Statistics, 36(1): 226–235, 1965. doi: 10.1214/aoms/1177700285.DOI
  10. [11]Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1):1–122, 2012. doi: 10.1561/2200000024.DOI
  11. [12]Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In Proceedings of the 20th International Conference on Algorithmic Learning Theory (ALT), volume 5809 of Lecture Notes in Computer Science, pages 23–37. Springer, 2009. doi: 10.1007/978-3-642-04414-4_7.DOI
  12. [13]Felipe Caro and Jérémie Gallien. Dynamic assortment with demand learning for seasonal consumer goods. Management Science, 53(2):276–292, 2007. doi: 10.1287/mnsc.1060.0613.DOI
  13. [14]Tanmoy Chakraborty, Eyal Even-Dar, Sudipto Guha, Yishay Mansour, and S. Muthukrishnan. Approximation schemes for sequential posted pricing in multi-unit auctions. In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE), volume 6484 of Lecture Notes in Computer Science. Springer, 2010. doi: 10.1007/978-3-642-17572-5_13.
  14. [15]Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. Mathematics of Operations Research, 33(4):945–964, 2008. URL https://www.jstor.org/stable/25578099.
  15. [16]Morris H. DeGroot. Uncertainty, information, and sequential experiments. The Annals of Mathematical Statistics, 33(2):404–419, 1962. doi: 10.1214/aoms/1177704567.DOI
  16. [17]Kun Deng, Chris Bourke, Stephen Scott, Julie Sunderman, and Yaling Zheng. Bandit-based algorithms for budgeted learning. In Proceedings of the 7th IEEE International Conference on Data Mining (ICDM), pages 463–468. IEEE Computer Society, 2007.DOI
  17. [18]Kun Deng, Yaling Zheng, Chris Bourke, Stephen Scott, and Julie Masciale. New algorithms for budgeted learning. Machine Learning, 90:59–90, 2013. doi: 10.1007/s10994-012-5299-2.DOI
  18. [19]David J. Eckman and Shane G. Henderson. Posterior-based stopping rules for Bayesian ranking-and-selection procedures. INFORMS Journal on Computing, 34(3):1711–1728, 2022. doi: 10.1287/ijoc.2021.1132.DOI
  19. [20]Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(39):1079–1105, 2006. URL https://jmlr.org/papers/v7/evendar06a.html.DOI
  20. [22]Peter I. Frazier, Warren B. Powell, and Savas Dayanik. A knowledge-gradient policy for sequential information collection. SIAM Journal on Control and Optimization, 47(5):2410–2439, 2008.DOI
  21. [23]Hao Fu, Jian Li, and Pan Xu. A PTAS for a class of stochastic dynamic programs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1–56:14, 2018. doi: 10.4230/LIPIcs.ICALP.2018.56.DOI
  22. [24]John Gittins, Kevin Glazebrook, and Richard Weber. Multi-Armed Bandit Allocation Indices. John Wiley & Sons, 2 edition, 2011. doi: 10.1002/9780470980033.DOI
  23. [27]Ashish Goel, Sudipto Guha, and Kamesh Munagala. How to probe for an extreme value. ACM Transactions on Algorithms, 2010. doi: 10.1145/1868237.1868250. URL https://users.cs.duke.edu/~kamesh/pods06_model.pdf.DOI
  24. [28]Russell Greiner, Adam J. Grove, and Dan Roth. Learning cost-sensitive active classifiers. Artificial Intelligence, 139:137–174, 2002.
  25. [29]Sudipto Guha and Kamesh Munagala. Approximation algorithms for budgeted learning problems. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 104–113, 2007. doi: 10.1145/1250790.1250807.DOI
  26. [30]Sudipto Guha and Kamesh Munagala. Sequential design of experiments via linear programming. arXiv:0805.2630, 2008. URL https://arxiv.org/abs/0805.2630.
  27. [31]Sudipto Guha and Kamesh Munagala. Multi-armed bandits with metric switching costs. In Automata, Languages and Programming, Part II, volume 5556 of Lecture Notes in Computer Science, pages 496–507. Springer, 2009. doi: 10.1007/978-3-642-02930-1_41.DOI
  28. [32]Sudipto Guha and Kamesh Munagala. Approximation algorithms for Bayesian multi-armed bandit problems. arXiv:1306.3525, 2013. URL https://arxiv.org/abs/1306.3525.
  29. [33]Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 7801 of Lecture Notes in Computer Science. Springer, 2013. doi: 10.1007/978-3-642-36694-9_18.DOI
  30. [34]Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, and R. Ravi. Approximation algorithms for correlated knapsacks and non-martingale bandits. In Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 827–836, 2011. URL https://arxiv.org/abs/1102.3749.
  31. [35]Nicholas Hay, Stuart Russell, David Tolpin, and Solomon Eyal Shimony. Selecting computations: Theory and applications. In Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pages 346–355, 2012. URL https://arxiv.org/abs/1207.5879.
  32. [36]L. Jeff Hong and Barry L. Nelson. The tradeoff between sampling and switching: New sequential procedures for indifference-zone selection. IIE Transactions, 37(7):623–634, 2005. doi: 10.1080/07408170590948486.DOI
  33. [37]Hideaki Ishibashi, Masayuki Karasuyama, Ichiro Takeuchi, and Hideitsu Hino. A stopping criterion for Bayesian optimization by the gap of expected minimum simple regrets. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 6463–6497, 2023. URL https://proceedings.mlr.press/v206/ishibashi23a.html.
  34. [38]Jaeyeon Jung, Vern Paxson, Arthur W. Berger, and Hari Balakrishnan. Fast portscan detection using sequential hypothesis testing. In Proceedings of the 2004 IEEE Symposium on Security and Privacy (S&P), pages 211–225. IEEE, 2004. doi: 10.1109/SECPRI.2004.1301325.DOI
  35. [39]Aloak Kapoor and Russell Greiner. Budgeted learning of bounded active classifiers. In Proceedings of the ACM SIGKDD Workshop on Utility-Based Data Mining, 2005a.
  36. [40]Aloak Kapoor and Russell Greiner. Learning and classifying under hard budgets. In Machine Learning: ECML 2005, volume 3720 of Lecture Notes in Computer Science, pages 170–181. Springer, 2005b. doi: 10.1007/11564096_20.DOI
  37. [41]Aloak Kapoor and Russell Greiner. Reinforcement learning for active model selection. In Proceedings of the ACM SIGKDD Workshop on Utility-Based Data Mining, pages 17–23, 2005c.DOI
  38. [42]Mohammad Reza Karimi, Nezihe Merve Gürel, Bojan Karlaš, Johannes Rausch, Ce Zhang, and Andreas Krause. Online active model selection for pre-trained classifiers. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130 of Proceedings of Machine Learning Research, 2021.arxiv.org/abs/2010.09818
  39. [43]Tomer Koren, Roi Livni, and Yishay Mansour. Multi-armed bandits with metric movement costs. In Advances in Neural Information Processing Systems, volume 30, 2017. URL https://proceedings.neurips.cc/paper_files/paper/2017/hash/bd0cc810b580b35884bd9d137c0e8b0f-Abstract.html.arxiv.org/abs/1710.08997
  40. [44]Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(185):1–52, 2018.
  41. [45]Zitian Li and Wang Chi Cheung. Best arm identification with resource constraints. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 253–261, 2024. URL https://proceedings.mlr.press/v238/li24c.html.arxiv.org/abs/2402.19090
  42. [46]Daniel J. Lizotte, Omid Madani, and Russell Greiner. Budgeted learning of naive-Bayes classifiers. In Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence (UAI), pages 378–385, 2003.
  43. [48]Omid Madani, Daniel J. Lizotte, and Russell Greiner. Active model selection. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (UAI), pages 357–365, 2004a.
  44. [50]Newton Mwai, Milad Malekipirbazari, and Fredrik D. Johansson. Understanding exploration in bandits with switching constraints: A batched approach in fixed-confidence pure exploration. European Workshop on Reinforcement Learning, 2025. URL https://newtonmwai.github.io/papers/4.pdf.
  45. [51]John W. Pratt. Risk aversion in the small and in the large. Econometrica, 32(1/2):122–136, 1964. doi: 10.2307/1913738.DOI
  46. [54]Maytal Saar-Tsechansky, Prem Melville, and Foster Provost. Active feature-value acquisition. Management Science, 55:664–684, 2009.
  47. [55]Leonard J. Savage. Elicitation of personal probabilities and expectations. Journal of the American Statistical Association, 66(336):783–801, 1971. doi: 10.1080/01621459.1971.10482346.DOI
  48. [56]Danny Segev and Sahil Singla. Efficient approximation schemes for stochastic probing and selection-stopping problems. Mathematics of Operations Research, 2025. doi: 10.1287/moor.2023.0242. Preliminary version in EC 2021; arXiv:2007.13121.DOI
  49. [57]David Simchi-Levi and Yunzong Xu. Phase transitions in bandits with switching constraints. Management Science, 69(12):7182–7201, 2023. doi: 10.1287/mnsc.2023.4755. URL https://arxiv.org/abs/1905.10825.
  50. [58]Herbert A. Simon. A behavioral model of rational choice. The Quarterly Journal of Economics, 69(1):99–118, 1955. doi: 10.2307/1884852.DOI
  51. [59]Abraham Wald. Sequential tests of statistical hypotheses. The Annals of Mathematical Statistics, 16(2):117–186, 1945. doi: 10.1214/aoms/1177731118.DOI
  52. [60]Martin L. Weitzman. Optimal search for the best alternative. Econometrica, 47(3):641–654, 1979.
  53. [61]Peter Whittle. Optimization over Time: Dynamic Programming and Stochastic Control, volume 2. John Wiley & Sons, 1983.
  54. [62]James T. Wilson. Stopping Bayesian optimization with probabilistic regret bounds. In Advances in Neural Information Processing Systems, volume 37, 2024. doi: 10.52202/079017-3118. URL https://arxiv.org/abs/2402.16811.
  55. [63]Qian Xie, Linda Cai, Alexander Terenin, Peter I. Frazier, and Ziv Scully. Cost-aware stopping for Bayesian optimization. In Proceedings of the 43rd International Conference on Machine Learning. PMLR, 2026. URL https://arxiv.org/abs/2507.12453.
  56. [64]Minlan Yu, Lavanya Jose, and Rui Miao. Software defined traffic measurement with opensketch. In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13), pages 29–42. USENIX Association, 2013.

Paper details

vlnc:W_vr2ubzxw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Multiple generative AI tools

View statement
Looking for related papers…
Contents