論文の概要: Indexability is Not Enough for Whittle: Improved, Near-Optimal
Algorithms for Restless Bandits
- arxiv url: http://arxiv.org/abs/2211.00112v1
- Date: Mon, 31 Oct 2022 19:35:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-02 13:34:44.969034
- Title: Indexability is Not Enough for Whittle: Improved, Near-Optimal
Algorithms for Restless Bandits
- Title（参考訳）: whittleにはインデクサビリティが不十分 - restless banditsのための改良されたほぼ最適アルゴリズム
- Authors: Abheek Ghosh, Dheeraj Nagaraj, Manish Jain, Milind Tambe
- Abstract要約: 本研究では,複数の行動を伴うレスレス・マルチアーム・バンディット(RMAB)の計画問題について検討する。
まず、Whittleインデックスポリシーは、シンプルで実用的な設定で失敗する可能性があることを示す。
次に,平均場法に基づく代替計画アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 30.532795983761314
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of planning restless multi-armed bandits (RMABs) with
multiple actions. This is a popular model for multi-agent systems with
applications like multi-channel communication, monitoring and machine
maintenance tasks, and healthcare. Whittle index policies, which are based on
Lagrangian relaxations, are widely used in these settings due to their
simplicity and near-optimality under certain conditions. In this work, we first
show that Whittle index policies can fail in simple and practically relevant
RMAB settings, \textit{even when} the RMABs are indexable. We discuss why the
optimality guarantees fail and why asymptotic optimality may not translate well
to practically relevant planning horizons.
We then propose an alternate planning algorithm based on the mean-field
method, which can provably and efficiently obtain near-optimal policies with a
large number of arms, without the stringent structural assumptions required by
the Whittle index policies. This borrows ideas from existing research with some
improvements: our approach is hyper-parameter free, and we provide an improved
non-asymptotic analysis which has: (a) no requirement for exogenous
hyper-parameters and tighter polynomial dependence on known problem parameters;
(b) high probability bounds which show that the reward of the policy is
reliable; and (c) matching sub-optimality lower bounds for this algorithm with
respect to the number of arms, thus demonstrating the tightness of our bounds.
Our extensive experimental analysis shows that the mean-field approach matches
or outperforms other baselines.
- Abstract（参考訳）: 本稿では,複数アクションによるレストレス・マルチアーム・バンディット(rmabs)の計画について検討する。
マルチチャネル通信や監視,マシンメンテナンスタスク,ヘルスケアといったアプリケーションを備えた,マルチエージェントシステムの一般的なモデルです。
ラグランジアン緩和に基づくウィトルインデックスポリシーは、特定の条件下での単純さとほぼ最適性のために、これらの設定で広く使用されている。
本稿では、WhittleインデックスポリシーがRMAB設定で失敗しうることを最初に示し、RMABがインデックス化可能である場合に \textit{even} を示す。
最適性保証が失敗した理由と漸近的最適性が実際に適切な計画地平線にうまく変換できない理由について考察する。
そこで我々は,Whittleインデックスポリシが要求する厳密な構造的仮定を必要とせず,多数のアームを持つ近似ポリシーを有効かつ効率的に得る平均場法に基づく代替計画アルゴリズムを提案する。
これは既存の研究からアイデアを借り、いくつかの改善を加えた:我々のアプローチはハイパーパラメータフリーであり、改善された非漸近分析を提供する。
a) 既知の問題パラメータに対する外因性ハイパーパラメータとより厳密な多項式依存の要件がないこと。
b) 政策の報奨が信頼できることを示す高確率境界,及び
(c)このアルゴリズムのアーム数に対する部分最適下界のマッチングにより、我々の境界の厳密さが証明される。
実験により, 平均場アプローチが他のベースラインと一致しているか, 上回っていることを示す。
関連論文リスト
- GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits [16.054685587034836]
GINO-Qは、レスレスマルチアームバンディット(RMAB)の最適指標ポリシーを学習するために設計された3段階近似アルゴリズムである。
GINO-QはRMABをインデックス化する必要がなく、柔軟性と適用性を高めている。
実験結果から, GINO-Q は非接種可能なRMABに対しても, ほぼ最適に学習できることが示唆された。
論文 参考訳（メタデータ） (2024-08-19T10:50:45Z) - Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs [9.58750210024265]
バンディットとマルコフ決定過程(MDP)に対する(確率的)ソフトマックスポリシー勾配(PG)法について検討する。
提案アルゴリズムは,技術結果と類似した理論的保証を提供するが,オラクルのような量の知識は必要としないことを示す。
マルチアームバンディット設定の場合,提案手法は明示的な探索や報奨ギャップの知識,報奨分布,ノイズを必要としない理論的なPGアルゴリズムを実現する。
論文 参考訳（メタデータ） (2024-05-21T18:12:39Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳（メタデータ） (2023-10-01T01:37:02Z) - Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits [55.03293214439741]
文脈的包帯では、エージェントは過去の経験に基づいた時間依存アクションセットから順次アクションを行う。
そこで本稿では,文脈的包帯のためのオンライン連続型ハイパーパラメータチューニングフレームワークを提案する。
理論上はサブ線形の後悔を達成でき、合成データと実データの両方において既存のすべての手法よりも一貫して優れた性能を発揮することを示す。
論文 参考訳（メタデータ） (2023-02-18T23:31:20Z) - Near-optimality for infinite-horizon restless bandits with many arms [19.12759228067286]
レスト・バンディットは、レコメンデーター・システム、アクティブ・ラーニング、収益管理などの分野での応用に関する問題である。
我々は、$O(sqrtN)$Optimity gapを持つ流体均衡政策と呼ばれる政策のクラスを導出する。
また,流体バランスポリシが特定の問題に対して最先端のパフォーマンスを実現することを実証的に示す。
論文 参考訳（メタデータ） (2022-03-29T18:49:21Z) - Reinforcement Learning for Finite-Horizon Restless Multi-Armed
Multi-Action Bandits [8.136957953239254]
本稿では、R(MA)2Bと呼ばれる複数の動作を持つ有限ホライゾンレス・マルチアームバンディット問題について検討する。
各アームの状態は、制御されたマルコフ決定プロセス(MDP)に従って進化し、アームを引く報酬は、対応するMDPの現在の状態と、取られたアクションの両方に依存する。
最適政策の発見は典型的には難解であるため,我々はOccupancy-Measured-Reward Index Policyと呼ぶ,計算に訴える指標ポリシーを提案する。
論文 参考訳（メタデータ） (2021-09-20T21:40:12Z) - On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。
信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。
最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
論文 参考訳（メタデータ） (2021-04-06T05:23:20Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Asymptotic Randomised Control with applications to bandits [0.0]
相関要素を持つ一般的なマルチアームバンディット問題を緩和制御問題として考察する。
エントロピー正規化を導入することにより、値関数への滑らかな近似が得られる。
これにより、最適決定過程の新たな半指数近似が得られる。
論文 参考訳（メタデータ） (2020-10-14T17:17:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。