論文の概要: Near-optimality for infinite-horizon restless bandits with many arms
- arxiv url: http://arxiv.org/abs/2203.15853v1
- Date: Tue, 29 Mar 2022 18:49:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-31 16:24:18.624738
- Title: Near-optimality for infinite-horizon restless bandits with many arms
- Title（参考訳）: 多数の腕を持つ無限ホリゾンレストレストバンディットの近接最適性
- Authors: Xiangyu Zhang, Peter I. Frazier
- Abstract要約: レスト・バンディットは、レコメンデーター・システム、アクティブ・ラーニング、収益管理などの分野での応用に関する問題である。
我々は、$O(sqrtN)$Optimity gapを持つ流体均衡政策と呼ばれる政策のクラスを導出する。
また,流体バランスポリシが特定の問題に対して最先端のパフォーマンスを実現することを実証的に示す。
- 参考スコア（独自算出の注目度）: 19.12759228067286
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Restless bandits are an important class of problems with applications in
recommender systems, active learning, revenue management and other areas. We
consider infinite-horizon discounted restless bandits with many arms where a
fixed proportion of arms may be pulled in each period and where arms share a
finite state space. Although an average-case-optimal policy can be computed via
stochastic dynamic programming, the computation required grows exponentially
with the number of arms $N$. Thus, it is important to find scalable policies
that can be computed efficiently for large $N$ and that are near optimal in
this regime, in the sense that the optimality gap (i.e. the loss of expected
performance against an optimal policy) per arm vanishes for large $N$. However,
the most popular approach, the Whittle index, requires a hard-to-verify
indexability condition to be well-defined and another hard-to-verify condition
to guarantee a $o(N)$ optimality gap. We present a method resolving these
difficulties. By replacing a global Lagrange multiplier used by the Whittle
index with a sequence of Lagrangian multipliers, one per time period up to a
finite truncation point, we derive a class of policies, called fluid-balance
policies, that have a $O(\sqrt{N})$ optimality gap. Unlike the Whittle index,
fluid-balance policies do not require indexability to be well-defined and their
$O(\sqrt{N})$ optimality gap bound holds universally without sufficient
conditions. We also demonstrate empirically that fluid-balance policies provide
state-of-the-art performance on specific problems.
- Abstract（参考訳）: restレスバンディット(restless bandits)は、レコメンダシステムやアクティブラーニング、収益管理などの分野におけるアプリケーションにおける重要な問題である。
我々は,各期間に一定数のアームを引っ張ることができ,アームが有限状態空間を共有するような多くのアームを持つ無限ホライゾンディスカウントレストレストバンディットを考える。
平均ケース最適ポリシーは確率的動的プログラミングによって計算できるが、必要な計算量は腕数$N$で指数関数的に増加する。
したがって、腕ごとの最適性ギャップ(つまり最適なポリシーに対する期待性能の喪失)が大きな$N$でなくなるという意味で、この体制において最も最適に近い、大規模な$N$で効率的に計算できるスケーラブルなポリシーを見つけることが重要である。
しかしながら、最も一般的なアプローチであるwhitle indexでは、検証の難しいインデクサビリティ条件が明確に定義され、またo(n)$の最適性ギャップを保証するための検証の難しい条件が必要である。
これらの課題を解決する方法を提案する。
ウィトル指数で用いられる大域ラグランジュ乗算器をラグランジアン乗算器の列に置き換えることにより、有限トランケート点までの時間周期に1つずつ、$O(\sqrt{N})$の最適性ギャップを持つ流体均衡ポリシと呼ばれるポリシーのクラスを導出する。
ウィットル・インデックスとは異なり、流体バランスのポリシーはインデクサビリティを適切に定義する必要がなく、その$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) - 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) - 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) - Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。
ソフトマージン条件下でのバニラQ関数の類似した結果を示す。
我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
論文 参考訳（メタデータ） (2023-02-05T14:22:41Z) - Indexability is Not Enough for Whittle: Improved, Near-Optimal
Algorithms for Restless Bandits [30.532795983761314]
本研究では,複数の行動を伴うレスレス・マルチアーム・バンディット(RMAB)の計画問題について検討する。
まず、Whittleインデックスポリシーは、シンプルで実用的な設定で失敗する可能性があることを示す。
次に,平均場法に基づく代替計画アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-31T19:35:15Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳（メタデータ） (2021-10-29T06:35:44Z) - Restless Bandits with Many Arms: Beating the Central Limit Theorem [25.639496138046546]
有限ホライズン・レスト・ブレイディット(有限ホライズン・レスト・ブレイディット)は、レコメンデーターシステム、アクティブラーニング、収益管理、その他多くの分野で重要な役割を果たしている。
最適ポリシーは、原理的には動的プログラミングを用いて計算できるが、計算に必要なスケールは腕数$N$で指数関数的にスケールする。
最適性ギャップが$O(1)$である流体プライオリティポリシと呼ばれる、非退化条件と、実用的に計算可能な新しいポリシーのクラスを特徴付ける。
論文 参考訳（メタデータ） (2021-07-25T23:27:12Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - 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) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。