A Classification View on Meta Learning Bandits

• URL: http://arxiv.org/abs/2504.04505v1
• Date: Sun, 06 Apr 2025 14:25:21 GMT
• Title: A Classification View on Meta Learning Bandits
• Abstract summary: We use an original classification view to meta learn interpretable and fast exploration plans for a fixed collection of bandits.<n>The test regret of the plan in contextual setting scales with $O (lambda-2 C_lambda) log2 (MH))$, being $M$ the size of $mathbbM$, $lambda$ a separation parameter over the bandits, and $C_lambda (mathbbM)$ a novel classification-coefficient.
• Score: 67.41789029784755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Contextual multi-armed bandits are a popular choice to model sequential decision-making. E.g., in a healthcare application we may perform various tests to asses a patient condition (exploration) and then decide on the best treatment to give (exploitation). When humans design strategies, they aim for the exploration to be fast, since the patient's health is at stake, and easy to interpret for a physician overseeing the process. However, common bandit algorithms are nothing like that: The regret caused by exploration scales with $\sqrt{H}$ over $H$ rounds and decision strategies are based on opaque statistical considerations. In this paper, we use an original classification view to meta learn interpretable and fast exploration plans for a fixed collection of bandits $\mathbb{M}$. The plan is prescribed by an interpretable decision tree probing decisions' payoff to classify the test bandit. The test regret of the plan in the stochastic and contextual setting scales with $O (\lambda^{-2} C_{\lambda} (\mathbb{M}) \log^2 (MH))$, being $M$ the size of $\mathbb{M}$, $\lambda$ a separation parameter over the bandits, and $C_\lambda (\mathbb{M})$ a novel classification-coefficient that fundamentally links meta learning bandits with classification. Through a nearly matching lower bound, we show that $C_\lambda (\mathbb{M})$ inherently captures the complexity of the setting.

Related papers

• Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set [93.03556214432615]
  In this paper, we revisit the linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process.<n>We propose a novel variance-adaptive algorithm textttVAEE for large action set, which actively explores actions that maximize the information gain.<n>We establish a nearly matching lower bound for the fixed action set setting indicating that emphharmonic-mean dependent rate is unavoidable.
  arXiv  Detail & Related papers  (2026-07-26T14:24:34Z)
• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• On the optimal regret of collaborative personalized linear bandits [15.661920010658626]
  This paper investigates the optimal regret achievable in collaborative personalized linear bandits.<n>We provide an information-theoretic lower bound that characterizes how the number of agents, the interaction rounds, and the degree of heterogeneity jointly affect regret.<n>Our results offer a complete characterization of when and how collaboration helps with a optimal regret bound.
  arXiv  Detail & Related papers  (2025-06-19T00:56:31Z)
• Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
  We develop a test based on low-regret algorithms and a nonasymptotic law of iterated logarithms. We prove that this test is reliable, and adapts to the signal level,' $Gamma,$ of any instance. We complement this by a minimax lower bound $(Omegad/Gamma2)$ for sample costs of reliable tests.
  arXiv  Detail & Related papers  (2024-06-21T20:56:35Z)
• Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
  We propose a Thompson sampling algorithm, named FGTS.CDB, for linear contextual dueling bandits. At the core of our algorithm is a new Feel-Good exploration term specifically tailored for dueling bandits. Our algorithm achieves nearly minimax-optimal regret, i.e., $tildemathcalO(dsqrt T)$, where $d$ is the model dimension and $T$ is the time horizon.
  arXiv  Detail & Related papers  (2024-04-09T04:45:18Z)
• Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration of the multi-armed bandit (R-CPE-MAB) problem. We introduce an algorithm named the Generalized Thompson Sampling Explore (GenTS-Explore) algorithm, which is the first algorithm that can work even when the size of the action set is exponentially large in $d$.
  arXiv  Detail & Related papers  (2023-08-20T11:56:02Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms [30.024167992890916]
  We study a decision where a learner faces a sequence of $K$-armed bandit tasks. The adversary is constrained to choose the optimal arm of each task in a smaller (but unknown) subset of $M$ arms. The boundaries might be known (the bandit meta-learning setting), or unknown (the non-stationary bandit setting)
  arXiv  Detail & Related papers  (2022-02-25T22:28:01Z)
• Maillard Sampling: Boltzmann Exploration Done Optimally [11.282341369957216]
  This thesis presents a randomized algorithm for the $K$-armed bandit problem. Maillard sampling (MS) computes the probability of choosing each arm in a closed form. We propose a variant of MS called MS$+$ that improves its minimax bound to $sqrtKTlogK$ without losing the optimality.
  arXiv  Detail & Related papers  (2021-11-05T06:50:22Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)
• Contextual Blocking Bandits [35.235375147227124]
  We study a novel variant of the multi-armed bandit problem, where at each time step, the player observes an independently sampled context that determines the arms' mean rewards. Playing an arm blocks it (across all contexts) for a fixed and known number of future time steps. We propose a UCB-based variant of the full-information algorithm that guarantees a $mathcalO(log T)$-regret w.r.t. an $alpha$regret strategy in $T time steps, matching the $Omega(log(T)$ lower bound
  arXiv  Detail & Related papers  (2020-03-06T20:34:42Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  We develop a meta-algorithm that selects between base algorithms. We show through a lower bound that even when one of the base algorithms has $O(sqrtT)$ regret, in general it is impossible to get better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2020-03-03T18:46:34Z)
• Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
  We consider the problem of $K$-armed dueling bandit in the contextual setting. We present two algorithms for the setup with respective regret guarantees.
  arXiv  Detail & Related papers  (2020-02-20T06:36:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.