論文の概要: The Countable-armed Bandit with Vanishing Arms
- arxiv url: http://arxiv.org/abs/2110.12118v1
- Date: Sat, 23 Oct 2021 02:47:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-26 16:33:24.233816
- Title: The Countable-armed Bandit with Vanishing Arms
- Title（参考訳）: 消滅する腕を持つ数え切れない腕のバンディット
- Authors: Anand Kalvit and Assaf Zeevi
- Abstract要約: 我々は、数え切れないほど多くの腕を有限個の「型」に分割したバンドイット問題を考える。
非定常分布は、腕の個体群における各腕型の相対的な存在量を支配しており、いわゆる「腕貯水池」である。
- 参考スコア（独自算出の注目度）: 8.099977107670918
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a bandit problem with countably many arms, partitioned into
finitely many "types," each characterized by a unique mean reward. A
"non-stationary" distribution governs the relative abundance of each arm-type
in the population of arms, aka the "arm-reservoir." This non-stationarity is
attributable to a probabilistic leakage of "optimal" arms from the reservoir
over time, which we refer to as the "vanishing arms" phenomenon; this induces a
time-varying (potentially "endogenous," policy-dependent) distribution over the
reservoir. The objective is minimization of the expected cumulative regret. We
characterize necessary and sufficient conditions for achievability of
sub-linear regret in terms of a critical vanishing rate of optimal arms. We
also discuss two reservoir distribution-oblivious algorithms that are
long-run-average optimal whenever sub-linear regret is statistically
achievable. Numerical experiments highlight a distinctive characteristic of
this problem related to ex ante knowledge of the "gap" parameter (the
difference between the top two mean rewards): in contrast to the stationary
bandit formulation, regret in our setting may suffer substantial inflation
under adaptive exploration-based (gap-oblivious) algorithms such as UCB
vis-`a-vis their non-adaptive forced exploration-based (gap-aware) counterparts
like ETC.
- Abstract（参考訳）: 数え切れないほど多くの腕を持つバンディット問題を有限個の「型」に分け、それぞれにユニークな平均的な報酬を特徴付ける。
非定常分布(non-stationary distribution)は、武器の集団における各腕型の相対的な存在量を支配しており、いわゆる「アーム貯水池」(arm-reservoir)である。
この非定常性は、貯水池から時間とともに「最適」の腕が漏れる確率的原因であり、これは「破壊的腕」現象と呼ばれ、貯水池に時間的変動(潜在的に「内在的」、政策依存的)な分布をもたらす。
目的は、予想される累積的後悔の最小化である。
我々は,最適アームの臨界消滅率の観点から,サブ線形後悔の達成に必要な,十分な条件を特徴付ける。
また,サブリニアな後悔が統計的に達成可能な場合,長ラン平均最適である2つの貯水池分布楕円型アルゴリズムについても検討した。
定常バンドイットの定式化とは対照的に,我々の設定における後悔は,UTB vis-`a-vis などの適応探索に基づくアルゴリズムの下では相当なインフレーションを被る可能性がある。
関連論文リスト
- Best Arm Identification with Minimal Regret [55.831935724659175]
最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。
エージェントの目標は、所定の信頼度で最高の腕を特定することである。
二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
論文 参考訳（メタデータ） (2024-09-27T16:46:02Z) - Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳（メタデータ） (2024-09-09T18:23:07Z) - Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
本研究は,有限個の腕を持つレスレス・マルチアーム・バンディット・セッティングにおけるベスト・アーム識別について検討する。
各アームによって生成された離散時間データは、共通の有限状態空間で値を取る同質マルコフ連鎖を形成する。
その結果,あるマルコフ決定過程の長期的挙動の追跡とその状態-行動的訪問比率が,逆および達成可能性境界を解析するための重要な要素であることが示唆された。
論文 参考訳（メタデータ） (2023-10-20T10:04:05Z) - Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget [4.226118870861363]
固定予算の下で、制約のある純粋な探索、多武装バンディットの定式化を検討する。
本稿では,Successive Rejects フレームワークに基づく textscConstrained-SR というアルゴリズムを提案する。
また, ある特別な場合において, 関連する崩壊速度は情報理論的下界に対してほぼ最適であることを示した。
論文 参考訳（メタデータ） (2022-11-27T08:58:16Z) - Beyond the Best: Estimating Distribution Functionals in Infinite-Armed
Bandits [40.71199236098642]
無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。
我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-11-01T18:20:10Z) - Reproducible Bandits [95.8830340560603]
バンディット環境におけるポリシーは、2つの異なる実行において全く同じ腕列を高い確率で引き出すと再現可能と呼ばれる。
再現可能なポリシが存在するだけでなく、時間的地平線の観点から、ほぼ同じ(再現不可能な)後悔境界を達成することを示す。
以上の結果から,無作為化が探索・探索トレードオフに不可欠であるにもかかわらず,同一の腕を2回の異なるラウンドで引き抜いて最適なバランスをとれることが示唆された。
論文 参考訳（メタデータ） (2022-10-04T20:36:45Z) - A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit [1.2183405753834562]
この研究は、両腕のベルヌーイ・バンディット問題(英語版)(Bernoulli bandit problem)の、腕の手段の和が1であるバージョンに対処する。
我々は, それぞれの問題を線形熱方程式の解に関連付けることにより, minmax最適後悔と擬似回帰の先行順序項を得る。
論文 参考訳（メタデータ） (2022-02-11T17:03:18Z) - From Finite to Countable-Armed Bandits [8.099977107670918]
有限の型に属する数え切れないほど多くのアームを持つバンドイット問題を考える。
武器の集団のそれぞれの種類の割合を設定する型に一定の分布がある。
我々は,O(log n)分布依存的な累積後悔を任意の回数の再生後に達成する完全適応型オンライン学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-22T13:09:50Z) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳（メタデータ） (2021-05-22T02:46:04Z) - Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。
ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。
逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
論文 参考訳（メタデータ） (2020-06-22T16:06:25Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。