Document detail
ID

oai:arXiv.org:2408.15535

Topic
Computer Science - Machine Learnin... Computer Science - Artificial Inte...
Author
Jeong, Woojin Min, Seungki
Category

Computer Science

Year

2024

listing date

9/4/2024

Keywords
budgeted budget algorithms sampling thompson
Metrics

Abstract

We consider a Bayesian budgeted multi-armed bandit problem, in which each arm consumes a different amount of resources when selected and there is a budget constraint on the total amount of resources that can be used.

Budgeted Thompson Sampling (BTS) offers a very effective heuristic to this problem, but its arm-selection rule does not take into account the remaining budget information.

We adopt \textit{Information Relaxation Sampling} framework that generalizes Thompson Sampling for classical $K$-armed bandit problems, and propose a series of algorithms that are randomized like BTS but more carefully optimize their decisions with respect to the budget constraint.

In a one-to-one correspondence with these algorithms, a series of performance benchmarks that improve the conventional benchmark are also suggested.

Our theoretical analysis and simulation results show that our algorithms (and our benchmarks) make incremental improvements over BTS (respectively, the conventional benchmark) across various settings including a real-world example.

;Comment: accepted

Jeong, Woojin,Min, Seungki, 2024, Improving Thompson Sampling via Information Relaxation for Budgeted Multi-armed Bandits

Document

Open

Share

Source

Articles recommended by ES/IODE AI

Comparison between Dual-Energy CT and Quantitative Susceptibility Mapping in Assessing Brain Iron Deposition in Parkinson Disease
nigra substantia healthy depositions p < 05 nucleus brain susceptibility ct bilateral dual-energy iron quantitative mapping values magnetic globus pallidus
Integration of human papillomavirus associated anal cancer screening into HIV care and treatment program in Pakistan: perceptions of policymakers, managers, and care providers
hpv hiv msm transgender women anal cancer screening integration pakistan system managers pakistan informants anal screening cancer lack healthcare hiv