論文の概要: Reinforcement learning with combinatorial actions for coupled restless bandits
- arxiv url: http://arxiv.org/abs/2503.01919v2
- Date: Mon, 17 Mar 2025 22:59:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-19 16:29:11.260859
- Title: Reinforcement learning with combinatorial actions for coupled restless bandits
- Title(参考訳): 組み合わされたレスト・バンディットに対する組合せ行動による強化学習
- Authors: Lily Xu, Bryan Wilder, Elias B. Khalil, Milind Tambe,
- Abstract要約: 提案するSEQUOIAは,動作空間に対する長期報酬を直接最適化するRLアルゴリズムである。
我々は,複数介入,経路制約,二部間マッチング,容量制約という,制約を伴う4つの新しいレスレス・バンディット問題に対して,SEQUOIAを実証的に検証した。
- 参考スコア(独自算出の注目度): 62.89013331120493
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Reinforcement learning (RL) has increasingly been applied to solve real-world planning problems, with progress in handling large state spaces and time horizons. However, a key bottleneck in many domains is that RL methods cannot accommodate large, combinatorially structured action spaces. In such settings, even representing the set of feasible actions at a single step may require a complex discrete optimization formulation. We leverage recent advances in embedding trained neural networks into optimization problems to propose SEQUOIA, an RL algorithm that directly optimizes for long-term reward over the feasible action space. Our approach embeds a Q-network into a mixed-integer program to select a combinatorial action in each timestep. Here, we focus on planning over restless bandits, a class of planning problems which capture many real-world examples of sequential decision making. We introduce coRMAB, a broader class of restless bandits with combinatorial actions that cannot be decoupled across the arms of the restless bandit, requiring direct solving over the joint, exponentially large action space. We empirically validate SEQUOIA on four novel restless bandit problems with combinatorial constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints. Our approach significantly outperforms existing methods -- which cannot address sequential planning and combinatorial selection simultaneously -- by an average of 24.8\% on these difficult instances.
- Abstract(参考訳): 強化学習(Reinforcement Learning, RL)は、大規模な状態空間や時間的地平線を扱うことで、現実的な計画問題の解決に益々応用されている。
しかし、多くの領域において重要なボトルネックは、RL法が大規模で組合せ的に構造化された作用空間に対応できないことである。
このような設定では、単一のステップで実行可能なアクションの集合を表現することさえも、複雑な離散的な最適化の定式化を必要とするかもしれない。
我々は、トレーニングされたニューラルネットワークを最適化問題に組み込む最近の進歩を活用し、実行可能なアクション空間に対する長期的な報酬を直接最適化するRLアルゴリズムであるSEQUOIAを提案する。
提案手法では,Q-networkを混合整数プログラムに組み込んで,各タイミングで組合せ動作を選択する。
ここでは、シーケンシャルな意思決定の現実的な例を多く捉えた、レスト・バンディット(restless bandits)の計画に焦点をあてる。
我々は、より広範なレスト・バンディットのクラスであるcoRMABを紹介し、この組み合わせ行動は、レスト・バンディットの腕間では分離できず、関節と指数関数的に大きなアクション空間を直接解決する必要がある。
我々は,複数介入,経路制約,二部マッチング,容量制約の4つの新しいレスレスト・バンディット問題に対して,SEQUOIAを実証的に検証した。
提案手法は, 逐次計画と組合せ選択を同時に処理できない既存手法を, これらの難易度に対して平均24.8\%で上回っている。
関連論文リスト
- Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization [17.392822956504848]
マルチエージェントタスクのための高品質なソリューションを効率的に構築するための強化学習フレームワークを提案する。
PARCOは,(1)並列ソリューション構築において効果的なエージェント協調を可能にするトランスフォーマーベースの通信層,(2)低レイテンシ,並列エージェント決定のためのマルチポインタ機構,(3)優先度ベースのコンフリクトハンドラの3つの重要なコンポーネントを統合する。
提案手法が最先端の学習手法より優れているマルチエージェント車両ルーティングおよびスケジューリング問題においてPARCOを評価し,強力な一般化能力と計算効率を示す。
論文 参考訳(メタデータ) (2024-09-05T17:49:18Z) - Accelerating Search-Based Planning for Multi-Robot Manipulation by Leveraging Online-Generated Experiences [20.879194337982803]
MAPF(Multi-Agent Path-Finding)アルゴリズムは、離散的な2Dドメインで保証され、厳密な保証を提供する。
本稿では,その反復的かつ漸進的な性質を活用して,競合に基づく探索アルゴリズムを高速化する手法を提案する。
論文 参考訳(メタデータ) (2024-03-29T20:31:07Z) - Efficient Planning in Combinatorial Action Spaces with Applications to
Cooperative Multi-Agent Reinforcement Learning [16.844525262228103]
協調型マルチエージェント強化学習では、多数のエージェントが共同でグローバル報酬関数を最適化し、エージェントの数によってアクション空間が爆発する。
最小限の要件として、モデルクラスの任意のQ-関数に対する欲求ポリシーを効率的に計算できるargmaxオラクルへのアクセスを仮定する。
そこで本研究では,全ての問題パラメータの計算と問合せを複雑化するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-08T23:42:49Z) - Deep Policy Iteration with Integer Programming for Inventory Management [8.27175065641495]
本稿では,大規模なアクセス可能な行動空間と状態依存制約を用いた長期割引報酬問題を最適化するための枠組みを提案する。
提案したプログラム可能なアクター強化学習(PARL)は,ニューラルネットワーク(NN)を利用して値関数を近似するディープ・ポリシー法を用いる。
我々は、提案アルゴリズムを最先端のRLアルゴリズムに対してベンチマークし、一般的に補充を使い、既存の手法を平均14.7%も上回っていることを発見した。
論文 参考訳(メタデータ) (2021-12-04T01:40:34Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳(メタデータ) (2021-03-10T03:16:12Z) - Reinforcement Learning with Combinatorial Actions: An Application to
Vehicle Routing [9.995347522610674]
我々は,強化行動空間を用いた価値関数に基づく深層強化学習の枠組みを開発する。
キャパシタン化車両ルーティング問題(CVRP)に対するこの枠組みの適用について述べる。
それぞれの事例において、アクションを単一ルートの構築としてモデル化し、単純なポリシーアルゴリズムによって改善される決定論的ポリシーを考える。
論文 参考訳(メタデータ) (2020-10-22T19:32:21Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep
Reinforcement Learning [102.78958681141577]
SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。
SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
論文 参考訳(メタデータ) (2020-07-09T17:08:44Z) - Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot
Transfer [71.44215606325005]
本稿では,シーケンシャルなサブゴールタスクの超指数空間における解を高速に計算するための,Jump-Operator Dynamic Programmingという新しいフレームワークを提案する。
このアプローチでは、時間的に拡張された行動として機能する、再利用可能な目標条件付き警察のアンサンブルを制御する。
すると、この部分空間上の目的関数のクラスを、解がグラウンド化に不変であるものとして特定し、最適ゼロショット移動をもたらす。
論文 参考訳(メタデータ) (2020-07-06T05:13:20Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳(メタデータ) (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。