論文の概要: Restless Bandits with Many Arms: Beating the Central Limit Theorem
- arxiv url: http://arxiv.org/abs/2107.11911v1
- Date: Sun, 25 Jul 2021 23:27:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-27 23:27:48.591407
- Title: Restless Bandits with Many Arms: Beating the Central Limit Theorem
- Title（参考訳）: 多くの腕を持つレストなしバンディット:中央極限定理を破る
- Authors: Xiangyu Zhang, Peter I. Frazier
- Abstract要約: 有限ホライズン・レスト・ブレイディット(有限ホライズン・レスト・ブレイディット)は、レコメンデーターシステム、アクティブラーニング、収益管理、その他多くの分野で重要な役割を果たしている。
最適ポリシーは、原理的には動的プログラミングを用いて計算できるが、計算に必要なスケールは腕数$N$で指数関数的にスケールする。
最適性ギャップが$O(1)$である流体プライオリティポリシと呼ばれる、非退化条件と、実用的に計算可能な新しいポリシーのクラスを特徴付ける。
- 参考スコア（独自算出の注目度）: 25.639496138046546
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider finite-horizon restless bandits with multiple pulls per period,
which play an important role in recommender systems, active learning, revenue
management, and many other areas. While an optimal policy can be computed, in
principle, using dynamic programming, the computation required scales
exponentially in the number of arms $N$. Thus, there is substantial value in
understanding the performance of index policies and other policies that can be
computed efficiently for large $N$. We study the growth of the optimality gap,
i.e., the loss in expected performance compared to an optimal policy, for such
policies in a classical asymptotic regime proposed by Whittle in which $N$
grows while holding constant the fraction of arms that can be pulled per
period. Intuition from the Central Limit Theorem and the tightest previous
theoretical bounds suggest that this optimality gap should grow like
$O(\sqrt{N})$. Surprisingly, we show that it is possible to outperform this
bound. We characterize a non-degeneracy condition and a wide class of novel
practically-computable policies, called fluid-priority policies, in which the
optimality gap is $O(1)$. These include most widely-used index policies. When
this non-degeneracy condition does not hold, we show that fluid-priority
policies nevertheless have an optimality gap that is $O(\sqrt{N})$,
significantly generalizing the class of policies for which convergence rates
are known. We demonstrate that fluid-priority policies offer state-of-the-art
performance on a collection of restless bandit problems in numerical
experiments.
- Abstract（参考訳）: 我々は,レコメンダシステム,アクティブラーニング,収益管理,その他多くの分野において重要な役割を担っている,周期毎に複数のプルを持つ有限ホリゾンレストレスバンディットを考える。
最適ポリシーは、原理的には動的プログラミングを用いて計算できるが、計算に必要なスケールは腕数$N$で指数関数的にスケールする。
したがって、大規模な$N$で効率的に計算できるインデックスポリシーやその他のポリシーのパフォーマンスを理解することにはかなり価値がある。
ホイットルが提唱した古典的漸近的体制において, 最適性ギャップの増大,すなわち, 最適政策と比較して期待性能の損失について検討し, 周期ごとに引き出すことのできるアームの比率を一定に保ちながら, n$ を増加させる。
中心極限定理と最も厳密な前の理論境界からの直観は、この最適性ギャップは$o(\sqrt{n})$ のように成長することを示唆する。
驚くべきことに、我々はこの限界を上回ることができることを示す。
我々は,非退化条件と,その最適性差が $o(1)$ である流体優先性ポリシーと呼ばれる,新しい実用計算可能な政策の幅広いクラスを特徴付ける。
これらは最も広く使われているインデックスポリシーを含んでいる。
この非退化条件が成立しない場合、流体優先性ポリシーは、しかしながら、o(\sqrt{n})$である最適性ギャップを持ち、収束率が知られているポリシーのクラスを著しく一般化する。
数値実験において,流体プライオリティポリシはレストレスバンディット問題の集合に対して最先端の性能を提供することを示した。
関連論文リスト
- Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption [11.41663079285674]
両腕の動的部分集合を2つ維持する新しいアンフツーセットポリシーを提案する。
2組のポリシーは、$O(exp(-C N)$Optimity gap for a $N$-armed problem で最適であることを示す。
論文 参考訳（メタデータ） (2024-05-28T07:08:29Z) - Oracle-Efficient Reinforcement Learning for Max Value Ensembles [7.404901768256101]
大または無限の状態空間における強化学習(RL)は、理論上、実験的に困難である。
この作業では、$textitmax-following Policy$と競合することを目指しています。
我々の主な成果は、構成ポリシーのみにアクセスすると、最大フォローポリシーと競合する効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2024-05-27T01:08:23Z) - Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits [11.41663079285674]
我々のポリシーは、$O(1/sqrtN)$Optimity gap for a $N$-armed problemで最適であることを示す。
当社のアプローチは、インデックスや優先順位ポリシーに重点を置く既存の作業から逸脱しています。
論文 参考訳（メタデータ） (2024-02-08T14:07:20Z) - Theoretical guarantees on the best-of-n alignment policy [110.21094183592358]
基本方針と最良$n$ポリシーのKL分散は、$log (n) - (n-1)/n.$と等しいことを示す。
KLの発散に対する新しい推定器を提案し、いくつかの例を通して厳密な近似を与えることを実証的に示す。
論文 参考訳（メタデータ） (2024-01-03T18:39:13Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Restless Bandits with Average Reward: Breaking the Uniform Global
Attractor Assumption [12.471848976031904]
基本的な目標は、腕の数($N$)が大きくなるにつれて、最適性のギャップを小さくするポリシーを効率的に計算することである。
既存の最適性に関する結果は、すべて一様大域的誘引特性(UGAP)に依存している。
我々は,任意の単一武器のポリシーを元の$N$武器の問題に対するポリシーに変換する,汎用的なシミュレーションベースのフレームワークを提案する。
論文 参考訳（メタデータ） (2023-05-31T21:26:43Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-19T01:09:24Z) - Near-optimality for infinite-horizon restless bandits with many arms [19.12759228067286]
レスト・バンディットは、レコメンデーター・システム、アクティブ・ラーニング、収益管理などの分野での応用に関する問題である。
我々は、$O(sqrtN)$Optimity gapを持つ流体均衡政策と呼ばれる政策のクラスを導出する。
また,流体バランスポリシが特定の問題に対して最先端のパフォーマンスを実現することを実証的に示す。
論文 参考訳（メタデータ） (2022-03-29T18:49:21Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳（メタデータ） (2021-10-29T06:35:44Z) - Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
Softmax Policy gradient(PG)メソッドは、現代の強化学習におけるポリシー最適化の事実上の実装の1つです。
ソフトマックス PG 法は、$mathcalS|$ および $frac11-gamma$ の観点から指数時間で収束できることを実証する。
論文 参考訳（メタデータ） (2021-02-22T18:56:26Z) - Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds
Globally Optimal Policy [95.98698822755227]
本研究は,リスクに敏感な深層強化学習を,分散リスク基準による平均報酬条件下で研究する試みである。
本稿では,ポリシー,ラグランジュ乗算器,フェンシェル双対変数を反復的かつ効率的に更新するアクタ批判アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-28T05:02:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。