A Complete Characterization of Learnability for Stochastic Noisy Bandits

• URL: http://arxiv.org/abs/2410.09597v1
• Date: Sat, 12 Oct 2024 17:23:34 GMT
• Title: A Complete Characterization of Learnability for Stochastic Noisy Bandits
• Authors: Steve Hanneke, Kun Wang,
• Abstract summary: We study the noisy bandit problem with an unknown reward function $f*$ in a known function class $mathcalF$. We give a complete characterization of learnability for model classes with arbitrary noise. We also prove adaptivity is sometimes necessary to achieve the optimal query complexity.
• Score: 19.35221816408955
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the stochastic noisy bandit problem with an unknown reward function $f^*$ in a known function class $\mathcal{F}$. Formally, a model $M$ maps arms $\pi$ to a probability distribution $M(\pi)$ of reward. A model class $\mathcal{M}$ is a collection of models. For each model $M$, define its mean reward function $f^M(\pi)=\mathbb{E}_{r \sim M(\pi)}[r]$. In the bandit learning problem, we proceed in rounds, pulling one arm $\pi$ each round and observing a reward sampled from $M(\pi)$. With knowledge of $\mathcal{M}$, supposing that the true model $M\in \mathcal{M}$, the objective is to identify an arm $\hat{\pi}$ of near-maximal mean reward $f^M(\hat{\pi})$ with high probability in a bounded number of rounds. If this is possible, then the model class is said to be learnable. Importantly, a result of \cite{hanneke2023bandit} shows there exist model classes for which learnability is undecidable. However, the model class they consider features deterministic rewards, and they raise the question of whether learnability is decidable for classes containing sufficiently noisy models. For the first time, we answer this question in the positive by giving a complete characterization of learnability for model classes with arbitrary noise. In addition to that, we also describe the full spectrum of possible optimal query complexities. Further, we prove adaptivity is sometimes necessary to achieve the optimal query complexity. Last, we revisit an important complexity measure for interactive decision making, the Decision-Estimation-Coefficient \citep{foster2021statistical,foster2023tight}, and propose a new variant of the DEC which also characterizes learnability in this setting.

Related papers

• Partial Identifiability and Misspecification in Inverse Reinforcement Learning [64.13583792391783]
  The aim of Inverse Reinforcement Learning is to infer a reward function $R$ from a policy $pi$. This paper provides a comprehensive analysis of partial identifiability and misspecification in IRL.
  arXiv  Detail & Related papers  (2024-11-24T18:35:46Z)
• Online Learning of Halfspaces with Massart Noise [47.71073318490341]
  We study the task of online learning in the presence of Massart noise. We present a computationally efficient algorithm that achieves mistake bound $eta T + o(T)$. We use our Massart online learner to design an efficient bandit algorithm that obtains expected reward at least $(1-1/k) Delta T - o(T)$ bigger than choosing a random action at every round.
  arXiv  Detail & Related papers  (2024-05-21T17:31:10Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs) Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
  arXiv  Detail & Related papers  (2022-10-05T22:52:00Z)
• Model Selection in Reinforcement Learning with General Function Approximations [10.97775622611135]
  We consider model selection for Reinforcement Learning environments -- Multi Armed Bandits (MABs) and Markov Decision Processes (MDPs) In the model selection framework, we do not know the function classes, denoted by $mathcalF$ and $mathcalM$, where the true models lie. We show that the cumulative regret of our adaptive algorithms match to that of an oracle which knows the correct function classes.
  arXiv  Detail & Related papers  (2022-07-06T21:52:07Z)
• Benefits of Additive Noise in Composing Classes with Bounded Capacity [5.127183254738711]
  We show that adding a small amount of Gaussian noise to the output of $mathcalF$ before composing it with $mathcalH$ can effectively control the capacity of $mathcalH circ mathcalF$. Preliminary empirical results on MNIST dataset indicate that the amount of noise required to improve over existing uniform bounds can be numerically negligible.
  arXiv  Detail & Related papers  (2022-06-14T22:57:02Z)
• Model Selection with Near Optimal Rates for Reinforcement Learning with General Model Classes [27.361399036211694]
  We address the problem of model selection for the finite horizon episodic Reinforcement Learning (RL) problem. In the model selection framework, instead of $mathcalP*$, we are given $M$ nested families of transition kernels. We show that textttARL-GEN obtains a regret of $TildemathcalO(d_mathcalE*H2+sqrtd_mathcalE* mathbbM* H2 T)$
  arXiv  Detail & Related papers  (2021-07-13T05:00:38Z)
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model [3.749193647980305]
  This paper considers a Markov decision process (MDP) that admits a set of state-action features. We show that a model-based approach (resp.$$Q-learning) provably learns an $varepsilon$-optimal policy with high probability.
  arXiv  Detail & Related papers  (2021-05-28T17:49:39Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Model-Based Reinforcement Learning with Value-Targeted Regression [48.92439657407732]
  We focus on finite-horizon episodic RL where the transition model $P$ belongs to a known family of models $mathcalP$. We derive a bound on the regret, which, in the special case of linear mixtures, the regret bound takes the form $tildemathcalO(dsqrtH3T)$.
  arXiv  Detail & Related papers  (2020-06-01T17:47:53Z)

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.