論文の概要: GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits
- arxiv url: http://arxiv.org/abs/2408.09882v1
- Date: Mon, 19 Aug 2024 10:50:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-20 16:44:56.764460
- Title: GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits
- Title（参考訳）: GINO-Q: レストレスマルチアームバンドにおける漸近的最適指標政策の学習
- Authors: Gongpu Chen, Soung Chang Liew, Deniz Gunduz,
- Abstract要約: GINO-Qは、レスレスマルチアームバンディット(RMAB)の最適指標ポリシーを学習するために設計された3段階近似アルゴリズムである。
GINO-QはRMABをインデックス化する必要がなく、柔軟性と適用性を高めている。
実験結果から, GINO-Q は非接種可能なRMABに対しても, ほぼ最適に学習できることが示唆された。
- 参考スコア（独自算出の注目度）: 16.054685587034836
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The restless multi-armed bandit (RMAB) framework is a popular model with applications across a wide variety of fields. However, its solution is hindered by the exponentially growing state space (with respect to the number of arms) and the combinatorial action space, making traditional reinforcement learning methods infeasible for large-scale instances. In this paper, we propose GINO-Q, a three-timescale stochastic approximation algorithm designed to learn an asymptotically optimal index policy for RMABs. GINO-Q mitigates the curse of dimensionality by decomposing the RMAB into a series of subproblems, each with the same dimension as a single arm, ensuring that complexity increases linearly with the number of arms. Unlike recently developed Whittle-index-based algorithms, GINO-Q does not require RMABs to be indexable, enhancing its flexibility and applicability. Our experimental results demonstrate that GINO-Q consistently learns near-optimal policies, even for non-indexable RMABs where Whittle-index-based algorithms perform poorly, and it converges significantly faster than existing baselines.
- Abstract（参考訳）: restless multi-armed bandit (RMAB) フレームワークは、様々な分野にまたがる一般的なモデルである。
しかし、その解法は(腕の数に関して)指数関数的に増大する状態空間と組合せ作用空間によって妨げられ、大規模インスタンスでは従来の強化学習法が実現不可能となる。
本稿では,RMABの漸近的最適指標法を学習するための3段階確率近似アルゴリズムであるGINO-Qを提案する。
GINO-QはRMABを1本の腕と同じ寸法の一連のサブプロブレムに分解することで次元の呪いを緩和し、腕の数とともに複雑さが線形に増加することを保証している。
最近開発されたWhittle-Indexベースのアルゴリズムとは異なり、GINO-QはRMABをインデックス化する必要がなく、柔軟性と適用性を高めている。
GINO-Q は,Whittle-index-based アルゴリズムが性能が悪く,既存のベースラインよりもはるかに高速に収束する非インデクサブル RMAB に対しても,常に準最適ポリシーを学習していることを示す。
関連論文リスト
- Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond [58.39457881271146]
CMAB(Multi-armed bandits)の多変量および確率的トリガーアーム(CMAB-MT)を用いた新しい枠組みを導入する。
CMAB-MTは既存のCMABと比べ、モデリング能力を高めるだけでなく、多変量確率変数の異なる統計特性を活用することで結果を改善することができる。
本フレームワークは, エピソード強化学習(RL)や商品分布の確率的最大カバレッジなど, 応用として多くの重要な問題を含むことができる。
論文 参考訳（メタデータ） (2024-06-03T14:48:53Z) - Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳（メタデータ） (2024-05-24T04:11:58Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Indexability is Not Enough for Whittle: Improved, Near-Optimal
Algorithms for Restless Bandits [30.532795983761314]
本研究では,複数の行動を伴うレスレス・マルチアーム・バンディット(RMAB)の計画問題について検討する。
まず、Whittleインデックスポリシーは、シンプルで実用的な設定で失敗する可能性があることを示す。
次に,平均場法に基づく代替計画アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-31T19:35:15Z) - Optimistic Whittle Index Policy: Online Learning for Restless Bandits [31.312043984489666]
遷移力学を学習するためのWhittleインデックスポリシーに基づく,最初のオンライン学習アルゴリズムを提案する。
我々のアルゴリズムUCWhittleは、RMABを未知の遷移で解くために、サブ線形$O(sqrtT log T)$の頻繁な後悔を実現する。
論文 参考訳（メタデータ） (2022-05-30T18:32:20Z) - 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) - Q-Learning Lagrange Policies for Multi-Action Restless Bandits [35.022322303796216]
RMAB(Multi-action restless multi-armed bandits)は、N$独立プロセスを管理する制約付きリソース割り当てのための強力なフレームワークである。
我々は,ラグランジアン緩和とQラーニングを組み合わせて,Multi-action RMABをオンラインで学習するための最初のアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-22T19:20:09Z) - Efficient Algorithms for Finite Horizon and Streaming Restless
Multi-Armed Bandit Problems [30.759279275710078]
インデックスベースのソリューションを計算するための新しいスケーラブルなアプローチを提案します。
コストのかかる有限地平線問題を解くことなく,指数減衰をキャプチャするアルゴリズムを提供する。
当社のアルゴリズムは、これらのタスクにおける既存の方法よりも150倍以上のスピードアップを実現し、パフォーマンスを損ないません。
論文 参考訳（メタデータ） (2021-03-08T13:10:31Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep
Reinforcement Learning [102.78958681141577]
SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。
SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
論文 参考訳（メタデータ） (2020-07-09T17:08:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。