betaFeedback

WorksComputer Science

Planned Restlessness: Delayed Meta Bandits with Budgets

Abstract

We study episodic finite-horizon Bayesian bandits, or meta-bandits, with independent arms. Each episode draws fresh arm qualities from unknown recurring priors. Observations arrive after known delays, and plays obey hard per-episode caps and total budgets. A play earns reward and informs both the current quality and the recurring prior: the learner must explore, use, and generalize. We formulate a common planning optimization over learning trajectories. Its LP relaxation values experiments through current reward, resource consumption and continuation: the value of future decisions from the learning state produced. Dual prices separate the arms into local programs and certify every admissible policy, including hierarchical Thompson sampling. Execution enforces the hard constraints while preserving the promised learning transitions or accounting for their loss. The framework also represents risk-sensitive objectives and prices purchased observations and buyout options. Delayed reports create planned restlessness: an arm's information changes while it is not played, through reports of its own earlier plays arriving on a known calendar. For stationary priors, finite reward alphabets, bounded report lag and nonbinding budgets, posterior sampling over the recurring priors bounds the price of not knowing them by O(N)O(\sqrt{N}) over NN episodes, with other parameters fixed. For one undelayed TT-step episode with arms capped at T/XT/X plays each, we obtain the LP-relative approximation factor 1+(2πX)−1/2+O(X−1)1+(2πX)^{-1/2}+O(X^{-1}), improving previous factors, with a matching lower bound for the leading term.

Introduction

We develop a common planning framework for episodic bandits over unknown recurring priors, incorporating delayed observations, hard per-arm budgets and per-episode caps, and risk-sensitive objectives beyond expected reward. In an episodic bandit or a meta-bandit problem there are nn unknown arms and a learner uses these arms over NN episodes, each with at most TT decision steps. Each episode draws fresh arm qualities from the recurring, initially unknown prior distribution. A single episode is a finite-horizon multi-armed bandit problem. At each step, the learner plays an arm, earns reward and generates an observation. The observation provides information about the current episode’s arm quality and, across episodes, its recurring prior. Therefore the typical multi-armed bandit tradeoff of explore/use now expands to explore, use, and generalize. Meta-bandits formalize this transfer/generalization by learning shared priors [7, 19, 25] using variants of Thompson sampling. Other examples include cold-start dynamic pricing [6], cloud management [31], database tuning across hardware environments [43], program synthesis [13], and LLM routing [41]. The analyzed MetaTS policy supplements Thompson sampling with a forced play of every arm in each task [25 Section 4.1]. HierTS avoids forced exploration in its sequential Gaussian analysis, but its concurrent guarantee again prescribes initial exploratory actions [19 Sections 6.1 and 6.3]. These methods share information through a hierarchical posterior, while their guarantees establish the learning produced by specified sampling and exploration rules. They do not explicitly optimize which observations are worth acquiring through their contribution to later feasible decisions. Even with independent arms, optimizing each episode separately can lose linearly in NN by never collecting observations valuable to later episodes (Examples A.1 and A.2).

We formulate a common planning objective that accounts for current reward, resource consumption and the continuation of learning. Its execution guarantee then accounts for the information and reward actually realized under the hard constraints.

Budgets are natural in distributed applications of episodic bandits. Budgeted learning is NP-hard even for a single episode with independent arms [16]. An unexpectedly long episode, or a favorable draw of an arm’s episode quality, can make immediate use attractive enough to exhaust the arm’s remaining budget. Those plays then become unavailable for learning and reward in later episodes. Per-episode caps limit this drawdown. Routing, coding, tuning and pricing also motivate risk-sensitive objectives beyond expected reward. Risk-sensitive objectives introduce a further structural difficulty. Mean–variance criteria need not satisfy Bellman’s principle of optimality, and maximizing expected return subject to a variance bound is NP-hard in finite-horizon Markov decision processes [27]. The objective depends on the return distribution across possible histories. Evaluating risk conditional on a sampled episode quality can discard variation that determines which action is preferable (Example A.6). Planning over outcome distributions retains this variation: fixed outcome scores enter as linear coefficients, while risk functionals act on the resulting law (Subsection 3.5).

Delays couple decisions within and across episodes. Concurrent Bayesian meta-bandits [19] analyze feedback withheld within a batch of decisions, and distributed optimization also motivates delayed feedback [2]. Delayed observation in learning dates back to Anderson [3]. Surprisingly, it was shown by Eick [12] that in the presence of delays an optimal policy can use a known arm and later return to an unknown arm. Thus the optimal policy of a delayed finite horizon multi-armed bandit problem is not a familiar stopping time problem [14], creating a foundational divergence from standard multi-armed bandits. A late-arriving observation changes an arm’s information even when the arm is not being played. This violates the standard rested-bandit assumption, and such arms are restless [40]. Caro and Yoo [9] study no-crossover delays. General restless bandits have no known tractable algorithms, and their decision versions are PSPACE-hard [30]. Here the delayed observations result from our own earlier plays and arrive on a calendar fixed in advance. We call this planned restlessness.

Budgets constrain resource use on every realized path; delays constrain the information available at each decision; risk criteria specify how the reward distribution is evaluated. Under this common model, we distinguish the losses due to unavailable information from the loss incurred by the algorithm. Let VeV_e be a policy’s reward in episode ee and VA=E∑eVeV_A = \mathbb{E}\sum_e V_e its expected total. Write VstateV_{\mathrm{state}} for the optimum when the recurring prior is revealed and each episode’s qualities are revealed at its start, VpriorV_{\mathrm{prior}} for the optimum when only the recurring prior is revealed, and VlearnV_{\mathrm{learn}} for the Bayes-optimal learner with our information. Then the overall loss decomposes as:

Vstate−VA=(Vstate−Vprior)+(Vprior−Vlearn)+(Vlearn−VA).(1)V_{\mathrm{state}} - V_A = (V_{\mathrm{state}} - V_{\mathrm{prior}}) + (V_{\mathrm{prior}} - V_{\mathrm{learn}}) + (V_{\mathrm{learn}} - V_A). \tag*{(1)}

The gap Vstate−VpriorV_{\mathrm{state}} - V_{\mathrm{prior}} is the cost of uncertainty about each episode’s fresh qualities. It can remain linear in NN even when the recurring law is known (Example A.7). The gap Vprior−VlearnV_{\mathrm{prior}} - V_{\mathrm{learn}} is the price of learning that law, and the largest fee worth paying to have it revealed before learning begins (Section 5.2). Under stationarity, independent arms, finite reward alphabets, bounded report lag and nonbinding budgets, this price is O(N)O(\sqrt{N}), and hence vanishes per episode (Proposition 5.4). The gap Vlearn−VAV_{\mathrm{learn}} - V_A is the algorithm’s loss under the same information and constraints. It measures how well the algorithm uses its information; Section 3 controls this loss for the learning-LP learner. Information is valuable only while the decisions it can improve remain available, and it is necessary that all three benchmarks face the same budgets, caps and report calendar.

We formulate a linear programming (LP) relaxation over learning trajectories. We assume independence across arms in this paper which permits separate arm programs coupled by expected episode capacities. The LP is written ex ante, over all possible observation records. Given the incoming belief, exchangeability and the fixed report calendar determine how each stopping record leads to the arm’s next learning state: its belief about the recurring prior, remaining budget and pending reports. Histories with the same sufficient state share these transitions and can be represented by one node. The transitions are specified before any particular outcome is observed; the policy determines the probability mass flowing through them. Current reward, resource use and continuation can therefore be accounted for linearly. Pricing the shared episode capacities separates the arms into local programs on their state DAGs (Figure 1). Their values are computed by backward induction, but their policies must be executed forward, echoing Kierkegaard’s distinction between understanding backward and living forward.2

One arm across an episode boundary

Figure 1. One arm across an episode boundary. Shown are selected stopping nodes uu of the current local DAG and starting nodes vv of the next. The handoff sends stopping mass z(u)z(u) through the fixed probabilities He(S,u,v)H_e(S,u,v), giving arrival masses q(v)q(v). The continuation is ∑vq(v)F(v)\sum_v q(v)F(v). Each next starting node carries its posterior, remaining budget and pending reports.

Execution proceeds ex post. The learner is an observer within the system it controls: its belief about the arms is itself part of the state being planned. Each play earns reward, spends budget and creates a report on the known calendar. The policy determines which evidence is acquired, when it becomes available, and which decisions remain feasible when it arrives. The belief from which the next episode is planned is therefore an output of the current policy. Budgets, delays and risk criteria constrain or evaluate this same process. The optimization trajectory is also a learning trajectory.

This coupling already drives the feedback restless bandits of Guha et al. [18]: the recurrent state process has a known transition law and evolves independently of the actions, while plays determine observations and future beliefs. Their approximation guarantees exploit further structure in the belief transitions. Liu and Zhao [26] establish indexability and derive closed-form indices for a related multichannel-access model. Meta-bandits extend this information problem across episodes: a play informs both the current quality and the recurring prior, and its value depends on the future decisions that its report can improve. Here planned restlessness supplies the structure for planning this evolution: reports from chosen plays change an arm’s learning state while other arms are played, on a known calendar. We plan the evolution of beliefs, budgets and pending reports jointly; execution must preserve the promised learning transitions or account for their loss. This action–information coupling is also central to dual control [24].

An observed outcome selects a branch already represented in the plan. If a local experiment is completed under the specified report calendar, it produces the promised law of next learning states. The next local program is valued under that premise. But the LP fits the arms’ workloads into an episode only in expectation, and the hard horizon may prevent completion. An unfinished experiment leaves the learner without some of the evidence used to value future decisions. It changes the decision problem from which the learner must continue. Execution must therefore preserve the learning transitions on which continuation was valued, or charge for their loss and continue from the information and resources actually available.3 Planning and execution thus have a predictor–corrector structure. The LP supplies the value and transition certificate; the executor enforces pathwise feasibility. In the classic Mizuno–Todd–Ye interior-point method, the predictor reduces the duality gap and the corrector restores centrality while retaining that reduction [29]. Here the quantity to protect is the value of future learning. Preserving continuation while approximating current reward lets the episode guarantees compose without multiplying their reward losses across episodes (Equation (21)).

The challenge of a proxy. The Bayes-optimal learner solves a joint program over the product of the arms’ state spaces. An algorithm therefore targets VpriorV_{\mathrm{prior}} through a proxy VproxyV_{\mathrm{proxy}}, the value of the decision problem it actually solves:

Vstate−VA=(Vstate−Vprior)+(Vprior−Vproxy)+(Vproxy−VA).(2)V_{\mathrm{state}} - V_A = (V_{\mathrm{state}} - V_{\mathrm{prior}}) + (V_{\mathrm{prior}} - V_{\mathrm{proxy}}) + (V_{\mathrm{proxy}} - V_A). \tag*{(2)}

The second term is the choice of proxy and the third is how much of it the algorithm realizes; Vproxy=VlearnV_{\mathrm{proxy}} = V_{\mathrm{learn}} recovers (1). The learning LP has value VLP≥VlearnV_{\mathrm{LP}} \ge V_{\mathrm{learn}}: it keeps the learner’s information but relaxes shared capacity and fast feedback. Its second term, (Vprior−Vlearn)−(VLP−Vlearn)(V_{\mathrm{prior}} - V_{\mathrm{learn}}) - (V_{\mathrm{LP}} - V_{\mathrm{learn}}), is signed, so the LP can value a learning program before we prove how much of it can be realized. Its third term is the leap from the LP certificate to a feasible learning policy. § 4 bounds this term; a guarantee VA≥αVLP−ϵV_A \ge\alpha V_{\mathrm{LP}} - \epsilon also gives VA≥αVlearn−ϵV_A \ge\alpha V_{\mathrm{learn}} - \epsilon, with no ordering between VLPV_{\mathrm{LP}} and VpriorV_{\mathrm{prior}}.

For posterior sampling, consider instead Vproxy=VTSV_{\mathrm{proxy}} = V_{\mathrm{TS}}, the reward of hierarchical Thompson sampling (HierTS) told the recurring prior. Meta-regret against a prior-informed Thompson-sampling rule measures VTS−VAV_{\mathrm{TS}} - V_A [6]; the allocation loss Vprior−VTSV_{\mathrm{prior}} - V_{\mathrm{TS}} remains. HierTS shares information across episodes [19]. Its sampled-mean rule chooses the feasible arm with largest sampled episode mean, using the reports received. Even with the recurring priors known, this rule loses at least NT/32NT/32 under delays and NT/12NT/12 under budgets and caps (Examples A.3 and A.5). Thus Vprior=VlearnV_{\mathrm{prior}} = V_{\mathrm{learn}} can coexist with a linear allocation loss. Evaluating risk conditional on a sampled episode quality also fails for mean–variance, CVaR and downside objectives (Example A.6). Appendix § 7 gives these comparisons, their calculations and the corresponding planning solutions. Bayes-regret analyses bound the complete loss against the best action for each realized task in their settings [7, 19, 25]. The LP’s prices and continuation values give a common certificate: every admissible policy’s shortfall splits into unused capacity and Bellman slacks. § 6.3 uses it to compare planning and execution, including HierTS.

Contributions

  • The Learning LP and risk generalizations. For general bounded reward distributions, we formulate a relaxation over learning trajectories. It decomposes into a backward cascade of the single-arm LPs of Guha and Munagala [17] (GM13 hereafter), linked by continuation values (Theorem 2.9). For explicit finite state graphs, its size is polynomial in their total size. Episode weights set the tradeoff between current reward and the later decisions improved by learning (§ 3.6). Bounded outcome scores enter linearly. For risk functionals, we identify the conditions for arm decomposition and execution.

  • Feasible execution. Full completion uses a time reserve whose leading lower bound matches as the caps grow; protecting selected reports avoids that reserve (§ 4). For a single undelayed episode, caps at most T/XT/X improve GM13’s factor 2 to 1+(2πX)−1/2+O(X−1)1 + (2\pi X)^{-1/2} + O(X^{-1}), with a matching leading lower bound. Fixed-order execution also permits up to KK distinct arms per step (Theorem 3.13). With arbitrary caps and delays at most δ\delta, the factor tends to 2 whenever δlog⁡δ=o(T)\delta\log\delta= o(T).

  • Learning-value stability and verified execution. The episode dual bounds planning-value error by the weighted total-variation error in observable experiment laws, with sharp constant 1. Protected reports transfer this comparison through execution, paying the single-episode factor once. Short probes give an executable O(N2/3)O(N^{2/3}) stationary comparison; the same argument permits drift (§ 5, Appendix § 9).

  • Information prices and predictive checks. Capacity prices bound a report’s value in the learning LP; repricing gives an exact nonnegative correction to its fixed-price valuation. Purchased reports and prior buyout enter the local programs. The price Vprior−VlearnV_{\mathrm{prior}}-V_{\mathrm{learn}} is O(N)O(\sqrt{N}) under Proposition 5.4’s assumptions, with other parameters fixed. A common dual certificate evaluates every admissible policy, including HierTS. Its reported innovations separate allocation loss from predictive error and support sequential model checks (§ 6).

Section 2 gives the model and learning LP; Section 3 develops execution and its extension to outcome scores. Section 4 proves stability and learning comparisons. Section 5 prices information and develops the policy certificates and predictive checks. Appendix A collects the illustrative examples and their planning solutions. The remaining appendices give execution proofs, statistical calculations and information-price bounds.

Other related work

Learning priors. Simchowitz et al. [38] bound the sensitivity of Bayesian decision rules to prior misspecification and derive meta-learning guarantees from prior estimation. Azizi et al. [5] study meta-learning for best-arm identification, using simple regret as the task objective.

Restless bandits and relaxations. Lagrangian relaxation separates weakly coupled dynamic programs by pricing their shared resources [1, 40]. Liu and Zhao [26] establish indexability for two-state Markov channels, and Caro and Yoo [9] study no-crossover response delays. Jung and Tewari [22] analyze posterior sampling for unknown restless dynamics in resetting episodes, relative to a chosen model-to-policy map. Jiang et al. [20] study unknown transition and reward laws with unobserved states, using a planning oracle. Paid state probes also appear in Guha et al. [18 Section 7].

Delayed and partial feedback. Joulani et al. [21] give reductions from delayed-feedback learning to algorithms for immediate feedback. Kalkanli and Özgür [23] analyze Thompson sampling with updates at batch boundaries. Impatient Bandits combines partial observations and delayed rewards through a predictive model [28, 42].

Model and the learning LP

Model

There are nn arms, indexed by i∈{1,…,n}i \in\{1,\ldots,n\}, and NN episodes, indexed by e∈{1,…,N}e \in\{1,\ldots,N\}. The planning horizon NN and positive integer episode lengths T1,…,TNT_1,\ldots,T_N are fixed and known before planning. Write T=(T1,…,TN)\mathbf{T}=(T_1,\ldots,T_N) and T=max⁡eTeT=\max_e T_e. At each step the learner plays one arm or waits. Waiting earns zero, uses no arm budget and allows scheduled reports to arrive. The LP below allows unequal known lengths. The execution and rate statements use the uniform case Te=TT_e=T unless stated otherwise.

Arm ii has an episode quality θi(e)\theta_i^{(e)} in a standard Borel parameter space Θi\Theta_i. Given that quality, its successive rewards have a known law Ki(θi(e), ⁣dy)K_i(\theta_i^{(e)},\mathop{}\!dy) on [0,1][0,1], with mean μi(θ)=∫yKi(θ,dy)\mu_i(\theta)=\int y K_i(\theta,dy). The quality specifies a reward distribution: taking Θi\Theta_i to be the probability measures on [0,1][0,1] and Ki(θ,⋅)=θK_i(\theta,\cdot)=\theta includes every bounded reward law. Successive plays consume an outcome tape (Yi,j(e))j≥1(Y_{i,j}^{(e)})_{j\ge1}, which may be sampled before execution. A play earns its outcome immediately, but the learner observes it only when its report arrives. The policy’s random coins are independent of the arms.

Assumption 2.1 (Independent prior sequences across arms). Arm ii has a random sequence of priors Pi=(Pi(e))e≥1\mathcal{P}_i=(P_i^{(e)})_{e\ge1} on Θi\Theta_i, with known law Q1,i\mathcal{Q}_{1,i}. These sequences are independent across arms. Conditional

on them, the qualities are independent with θi(e)∼Pi(e)\theta_i^{(e)} \sim P_i^{(e)}. Conditional on the qualities, tape entries are independent with law Ki(θi(e),⋅)K_i(\theta_i^{(e)}, \cdot).

The learner knows the meta-prior Q1=⨂iQ1,iQ_1 = \bigotimes_i Q_{1,i}, but not the realized priors. In the stationary case Pi(e)=PiP_i^{(e)} = P_i for every episode. There are then two levels of exchangeability: episodes are i.i.d. given the recurring prior, and plays within an episode are i.i.d. given its quality. Conversely, invariance of each arm’s infinite outcome array under permutations of episodes and of plays within each episode gives this hierarchy by the hierarchical de Finetti representation [4]. The model requires no parametric or conjugate family.

Arm ii has a total play budget BiB_i and a per-episode cap LiL_i, both nonnegative integers. Write B=(Bi)iB = (B_i)_i and Lˉ=max⁡iLi≤T\bar L = \max_i L_i \le T. If its remaining budget is bb, it can make at most min⁡{Li,Te,b}\min\{L_i, T_e, b\} plays in episode ee. Both limits hold on every realized path.

References

  1. [1]Daniel Adelman and Adam J. Mersereau. Relaxations of weakly coupled stochastic dynamic programs. Operations Research, 56(3):712–727, 2008. doi: 10.1287/opre.1070.0445.DOI
  2. [2]Alekh Agarwal and John C. Duchi. Distributed delayed stochastic optimization. In Advances in Neural Information Processing Systems 24 (NIPS 2011), volume 24, pages 873–881. Curran Associates, Inc., 2011.
  3. [3]T. W. Anderson. Sequential analysis with delayed observations. Journal of the American Statistical Association, 59(308):1006–1015, 1964. doi: 10.1080/01621459.1964.10480746.DOI
  4. [4]Tim Austin and Dmitry Panchenko. A hierarchical version of the de Finetti and Aldous–Hoover representations. Probability Theory and Related Fields, 159(3):809–823, 2014. doi: 10.1007/s00440-013-0521-0.DOI
  5. [5]Mohammadjavad Azizi, Branislav Kveton, Mohammad Ghavamzadeh, and Sumeet Katariya. Meta-learning for simple regret minimization. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), volume 37, pages 6709–6717, 2023. doi: 10.1609/aaai.v37i6.25823.DOI
  6. [6]Hamsa Bastani, David Simchi-Levi, and Ruihao Zhu. Meta dynamic pricing: Transfer learning across experiments. Management Science, 68(3):1865–1881, 2022. doi: 10.1287/mnsc.2021.4071.DOI
  7. [7]Soumya Basu, Branislav Kveton, Manzil Zaheer, and Csaba Szepesvári. No regrets for learning the prior in bandits. In Advances in Neural Information Processing Systems 34 (NeurIPS), 2021.arxiv.org/abs/2107.06196
  8. [8]Dorian Baudry, Romain Gautron, Emilie Kaufmann, and Odalric Maillard. Optimal Thompson sampling strategies for support-aware CVaR bandits. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 716–726. PMLR, 2021. URL https://proceedings.mlr.press/v139/baudry21a.html.
  9. [9]Felipe Caro and Onesun Steve Yoo. Indexability of bandit problems with response delays. Probability in the Engineering and Informational Sciences, 24(3):349–374, 2010. doi: 10.1017/S0269964810000021.DOI
  10. [10]Tanmoy Chakraborty, Eyal Even-Dar, Sudipto Guha, Yishay Mansour, and S. Muthukrishnan. Approximation schemes for sequential posted pricing in multi-unit auctions. In Internet and Network Economics (WINE 2010), volume 6484 of Lecture Notes in Computer Science, pages 158–169. Springer, 2010. doi: 10.1007/978-3-642-17572-5_13. URL https://arxiv.org/abs/1008.1616.
  11. [11]Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In Proceedings of the 30th International Conference on Machine Learning (ICML), volume 28 of Proceedings of Machine Learning Research, pages 151–159, 2013.
  12. [12]Stephen G. Eick. The two-armed bandit with delayed responses. The Annals of Statistics, 16(1):254–264, 1988.DOI
  13. [13]Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua B. Tenenbaum. DreamCoder: Bootstrapping inductive program synthesis with wake-sleep library learning. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI ’21, pages 835–850. Association for Computing Machinery, 2021. doi: 10.1145/3453483.3454080.DOI
  14. [14]John C. Gittins and David M. Jones. A dynamic allocation index for the sequential design of experiments. In Progress in Statistics, pages 241–266. North-Holland, 1974.
  15. [15]Sudipto Guha. Budgeted Bayesian bandits for future utilization. Preprint, 2026. arXiv:2610.24156.arxiv.org/abs/2610.24156
  16. [16]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
  17. [17]Sudipto Guha and Kamesh Munagala. Approximation algorithms for Bayesian multi-armed bandit problems. arXiv:1306.3525, 2013. URL https://arxiv.org/abs/1306.3525.
  18. [18]Sudipto Guha, Kamesh Munagala, and Peng Shi. Approximation algorithms for restless bandit problems. Journal of the ACM, 58(1), 2010. doi: 10.1145/1870103.1870106. Article 3. Preliminary version in SODA 2009; arXiv:0711.3861.DOI
  19. [19]Joey Hong, Branislav Kveton, Manzil Zaheer, and Mohammad Ghavamzadeh. Hierarchical Bayesian bandits. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151 of Proceedings of Machine Learning Research, 2022.arxiv.org/abs/2111.06929
  20. [20]Bowen Jiang, Bo Jiang, Jian Li, Tao Lin, Xinbing Wang, and Chenghu Zhou. Online restless bandits with unobserved states. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 15041–15066, 2023.
  21. [21]Pooria Joulani, András György, and Csaba Szepesvári. Online learning under delayed feedback. In Proceedings of the 30th International Conference on Machine Learning (ICML), 2013.arxiv.org/abs/1306.0686
  22. [22]Young Hun Jung and Ambuj Tewari. Regret bounds for Thompson sampling in episodic restless bandit problems. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.arxiv.org/abs/1905.12673
  23. [23]Cem Kalkankli and Ayfer Özgür. Batched Thompson sampling. In Advances in Neural Information Processing Systems 34 (NeurIPS), 2021.arxiv.org/abs/2110.00202
  24. [24]Edgar D. Klenske and Philipp Hennig. Dual control for approximate Bayesian reinforcement learning. Journal of Machine Learning Research, 17(127):1–30, 2016. URL https://www.jmlr.org/papers/v17/15-162.html.arxiv.org/abs/1510.03591
  25. [25]Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih-Wei Hsu, Martin Mladenov, Craig Boutilier, and Csaba Szepesvári. Meta-Thompson sampling. In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 5884–5893, 2021.arxiv.org/abs/2102.06129
  26. [26]Keqin Liu and Qing Zhao. Indexability of restless bandit problems and optimality of Whittle index for dynamic multichannel access. IEEE Transactions on Information Theory, 56(11):5547–5567, 2010. doi: 10.1109/TIT.2010.2068950. URL https://arxiv.org/abs/0810.4658.
  27. [27]Shie Mannor and John N. Tsitsiklis. Mean-variance optimization in Markov decision processes. In Proceedings of the 28th International Conference on Machine Learning, 2011. URL https://icml.cc/Conferences/2011/papers/156_icmlpaper.pdf.arxiv.org/abs/1104.5601
  28. [28]Thomas M. McDonald, Lucas Maystre, Mounia Lalmas, Daniel Russo, and Kamil Ciosek. Impatient bandits: Optimizing recommendations for the long-term without delay. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2023. doi: 10.1145/3580305.3599386.DOI
  29. [29]Shinji Mizuno, Michael J. Todd, and Yinyu Ye. On adaptive-step primal-dual interior-point algorithms for linear programming. Mathematics of Operations Research, 18(4):964–981, 1993. doi: 10.1287/moor.18.4.964.DOI
  30. [30]Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of optimal queuing network control. Mathematics of Operations Research, 24(2):293–305, 1999. doi: 10.1287/moor.24.2.293.DOI
  31. [31]Haoran Qiu, Weichao Mao, Archit Patke, Shengkun Cui, Chen Wang, Hubertus Franke, Zbigniew T. Kalbarczyk, Tamer Başar, and Ravishankar K. Iyer. FLASH: Fast model adaptation in ML-centric cloud platforms. In Proceedings of Machine Learning and Systems, volume 6, 2024.
  32. [32]Roy Radner and Joseph E. Stiglitz. A nonconcavity in the value of information. In Marcel Boyer and Richard E. Kihlstrom, editors, Bayesian Models in Economic Theory, pages 33–52. North-Holland, 1984.
  33. [33]R. Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2(3):21–41, 2000. doi: 10.21314/JOR.2000.038.DOI
  34. [34]Daniel Russo and Benjamin Van Roy. An information-theoretic analysis of Thompson sampling. Journal of Machine Learning Research, 17(68):1–30, 2016.
  35. [35]Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. Mathematics of Operations Research, 47(4), 2022.arxiv.org/abs/1803.02855
  36. [36]Glenn Shafer, Alexander Shen, Nikolai Vereshchagin, and Vladimir Vovk. Test martingales, Bayes factors and p-values. Statistical Science, 26(1):84–101, 2011. doi: 10.1214/10-STS347.DOI
  37. [37]Moshe Shaked and J. George Shanthikumar. Stochastic Orders. Springer, 2007.
  38. [38]Max Simchowitz, Christopher Tosh, Akshay Krishnamurthy, Daniel Hsu, Thodoris Lykouris, Miroslav Dudík, and Robert E. Schapire. Bayesian decision-making under misspecified priors with applications to meta-learning. In Advances in Neural Information Processing Systems 34 (NeurIPS), 2021.arxiv.org/abs/2107.01509
  39. [39]Richard D. Smallwood and Edward J. Sondik. The optimal control of partially observable markov processes over a finite horizon. Operations Research, 21(5):1071–1088, 1973. doi: 10.1287/opre.21.5.1071.DOI
  40. [40]Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of Applied Probability, 25(A):287–298, 1988.DOI
  41. [41]Jiahao Zeng, Ming Tang, and Ningning Ding. Learning to route llms from implicit cost-performance preferences via meta-learning. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, pages 6045–6053, 2026. doi: 10.24963/ijcai.2026/673.DOI
  42. [42]Kelly W. Zhang, Thomas Baldwin-McDonald, Kamil Ciosek, Lucas Maystre, and Daniel Russo. Impatient bandits: Optimizing for the long-term without delay. Journal of Machine Learning Research, 27(156):1–58, 2026.arxiv.org/abs/2501.07761
  43. [43]Xinyi Zhang, Hong Wu, Zhuo Chang, Shuowei Jin, Jian Tan, Feifei Li, Tieying Zhang, and Bin Cui. ResTune: Resource oriented tuning boosted by meta-learning for cloud databases. In Proceedings of the 2021 International Conference on Management of Data, SIGMOD ’21, pages 2102–2114. Association for Computing Machinery, 2021. doi: 10.1145/3448016.3457291.DOI
  44. [44]Qiuyu Zhu and Vincent Tan. Thompson sampling algorithms for mean-variance bandits. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 11599–11608. PMLR, 2020. URL https://proceedings.mlr.press/v119/zhu20d.html.arxiv.org/abs/2002.00232

Paper details

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

views · 4

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