論文の概要: A Complete Characterization of Learnability for Stochastic Noisy Bandits
- arxiv url: http://arxiv.org/abs/2410.09597v1
- Date: Sat, 12 Oct 2024 17:23:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-10-30 13:35:29.816266
- Title: A Complete Characterization of Learnability for Stochastic Noisy Bandits
- Title（参考訳）: 確率雑音帯域の学習性に関する一評価
- Authors: Steve Hanneke, Kun Wang,
- Abstract要約: 未知の報酬関数 $f*$ を既知の関数クラス $mathcalF$ で検討する。
任意の雑音を持つモデルクラスに対して、学習可能性の完全な評価を与える。
また、最適なクエリ複雑性を達成するためには適応性が必要であることも証明します。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 未知の報酬関数 $f^*$ を既知の関数クラス $\mathcal{F}$ において確率的雑音帯域問題を研究する。
形式的には、モデル$M$はアーム$\pi$を確率分布$M(\pi)$の報酬にマップする。
モデルクラス $\mathcal{M}$ はモデルの集合である。
M$ の各モデルに対して、平均報酬関数 $f^M(\pi)=\mathbb{E}_{r \sim M(\pi)}[r]$ を定義する。
バンディット学習問題では、各ラウンドごとに1つのアーム$\pi$を引いて、M(\pi)$からサンプリングされた報酬を観察する。
真のモデル $M\in \mathcal{M}$ を仮定する $\mathcal{M}$ の知識により、その目的は、有界なラウンド数において高い確率を持つ極大平均報酬 $f^M(\hat{\pi})$ をアーム $\hat{\pi}$ と同定することである。
これが可能であれば、モデルクラスは学習可能であると言われる。
重要なことに \cite{hanneke2023bandit} の結果は、学習可能性が決定不能なモデルクラスが存在することを示している。
しかし, モデルクラスは, 決定論的報酬を考慮し, 十分うるさいモデルを含むクラスに対して, 学習性は決定可能であるかという疑問を提起する。
任意の雑音を持つモデルクラスに対して、学習可能性の完全な評価を与えることで、この疑問に初めて肯定的に答える。
それに加えて、最適なクエリの複雑さの全スペクトルについても記述する。
さらに,最適なクエリ複雑性を実現するためには適応性が必要であることも証明する。
最後に、対話型意思決定のための重要な複雑さ尺度であるDecision-Estimation-Coefficient \citep{foster2021statistical,foster2023tight}を再検討し、この設定における学習性も特徴付ける新しいDECを提案する。
関連論文リスト
- Partial Identifiability and Misspecification in Inverse Reinforcement Learning [64.13583792391783]
Inverse Reinforcement Learning の目的は、報酬関数 $R$ をポリシー $pi$ から推論することである。
本稿では,IRLにおける部分的識別性と不特定性について包括的に分析する。
論文 参考訳（メタデータ） (2024-11-24T18:35:46Z) - Online Learning of Halfspaces with Massart Noise [47.71073318490341]
我々はMassartノイズの存在下でのオンライン学習の課題について検討する。
計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。
我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-05-21T17:31:10Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Model Selection in Reinforcement Learning with General Function
Approximations [10.97775622611135]
強化学習環境におけるモデル選択の検討 - マルチアームバンド(MAB)とマルコフ決定プロセス(MDP)-
モデル選択フレームワークでは、$mathcalF$と$mathcalM$で表される関数クラスを知らない。
適応アルゴリズムの累積的後悔は、正しい関数クラスを知っているオラクルの後悔と一致することを示す。
論文 参考訳（メタデータ） (2022-07-06T21:52:07Z) - Benefits of Additive Noise in Composing Classes with Bounded Capacity [5.127183254738711]
我々は、$mathcalH$で構成する前に$mathcalF$の出力に少量のガウスノイズを加えることで、$mathcalH circ mathcalF$を効果的に制御できることを示した。
MNISTデータセットの予備的な実験結果は、既存の一様境界よりも改善するために必要なノイズの量は数値的に無視可能であることを示している。
論文 参考訳（メタデータ） (2022-06-14T22:57:02Z) - Model Selection with Near Optimal Rates for Reinforcement Learning with
General Model Classes [27.361399036211694]
有限地平線エピソディック強化学習(RL)問題に対するモデル選択の問題に対処する。
モデル選択フレームワークでは、$mathcalP*$の代わりに、遷移カーネルのネストされたファミリーが$M$を与えられる。
textttARL-GENが$TildemathcalO(d_mathcalE* H2+sqrtd_mathcalE* mathbbM* H2T)$の後悔を得ることを示す。
論文 参考訳（メタデータ） (2021-07-13T05:00:38Z) - Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model [3.749193647980305]
本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
論文 参考訳（メタデータ） (2021-05-28T17:49:39Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Model-Based Reinforcement Learning with Value-Targeted Regression [48.92439657407732]
我々は、遷移モデル $P$ が既知のモデルの族 $mathcalP$ に属する有限水平エピソード RL に焦点を当てる。
線形混合の特別な場合において、後悔束は $tildemathcalO(dsqrtH3T)$ という形を取る。
論文 参考訳（メタデータ） (2020-06-01T17:47:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。