論文の概要: Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations
- arxiv url: http://arxiv.org/abs/2112.06517v1
- Date: Mon, 13 Dec 2021 09:48:54 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-15 01:06:15.456071
- Title: Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations
- Title（参考訳）: マルチ武装バンディットの「k$」ランキングトップはノイズ評価
- Authors: Evrard Garcelon and Vashist Avadhanula and Alessandro Lazaric and and
Matteo Pirotta
- Abstract要約: 我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。
評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
- 参考スコア（独自算出の注目度）: 95.38178351082657
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a multi-armed bandit setting where, at the beginning of each
round, the learner receives noisy independent, and possibly biased,
\emph{evaluations}
of the true reward of each arm and it selects $K$ arms with the objective of
accumulating as much reward as possible over $T$ rounds. Under the assumption
that at each round the true reward of each arm is drawn from a fixed
distribution, we derive different algorithmic approaches and theoretical
guarantees depending on how the evaluations are generated. First, we show a
$\widetilde{O}(T^{2/3})$ regret in the general case when the observation
functions are a genearalized linear function of the true rewards. On the other
hand, we show that an improved $\widetilde{O}(\sqrt{T})$ regret can be derived
when the observation functions are noisy linear functions of the true rewards.
Finally, we report an empirical validation that confirms our theoretical
findings, provides a thorough comparison to alternative approaches, and further
supports the interest of this setting in practice.
- Abstract（参考訳）: マルチアームのバンディット設定を考えると、各ラウンドの始めに、学習者は、各アームの真の報酬のノイズを独立的に受け取り、おそらくバイアスのある \emph{evaluations} を受け取り、できるだけ多くの報酬を t$ ラウンドに蓄積する目的で$k$ のアームを選択する。
各ラウンドにおいて、各アームの真の報酬が固定分布から引き出されるという仮定の下で、評価がどのように生成されるかによって異なるアルゴリズム的アプローチと理論的保証を導出する。
まず、観察関数が真の報酬の系式化された線形関数である場合の一般的な場合、$\widetilde{o}(t^{2/3})$ regretを示す。
一方,実報酬のノイズ線形関数が観測関数である場合には,改良された$\widetilde{o}(\sqrt{t})$ regretが得られることを示した。
最後に,理論的な知見を裏付ける実証的検証を報告し,代替手法を徹底的に比較し,実際にこの設定の関心をさらに支持する。
関連論文リスト
- Sparsity-Agnostic Linear Bandits with Adaptive Adversaries [19.84322270472381]
本研究では,各ラウンドにおいて,学習者が要素を選択して報酬を得る一連の行動(特徴ベクトル)を受信する線形帯域について検討する。
期待される報酬は、選択されたアクションの固定だが未知の線形関数である。
線形報酬関数の非ゼロ係数数$S$に依存するスパース後悔境界について検討する。
論文 参考訳（メタデータ） (2024-06-03T10:54:58Z) - Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Multi-Armed Bandits with Interference [39.578572123342944]
スイッチバックポリシは,最高の固定アームポリシに対して,最適に期待された後悔のO(sqrt T)$を達成できることが示される。
提案するクラスタランダム化ポリシは,期待値に最適である。
論文 参考訳（メタデータ） (2024-02-02T19:02:47Z) - Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文 参考訳（メタデータ） (2023-05-25T14:02:12Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - Beyond the Best: Estimating Distribution Functionals in Infinite-Armed
Bandits [40.71199236098642]
無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。
我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-11-01T18:20:10Z) - Provably Efficient Offline Reinforcement Learning with Trajectory-Wise
Reward [66.81579829897392]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。
PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。
私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-06-13T19:11:22Z) - A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits [11.918230810566945]
本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常的マルチアームバンディット問題について検討する。
我々は、$K$の武器付きバンディット問題において、ほぼ最適の$widetilde O(sqrtK N(S+1))$ dynamic regretを実現する方法を提案する。
論文 参考訳（メタデータ） (2022-01-17T17:23:56Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。