論文の概要: Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback
- arxiv url: http://arxiv.org/abs/2405.00950v1
- Date: Thu, 2 May 2024 02:20:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-03 18:14:01.342527
- Title: Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback
- Title(参考訳): 未知遷移と帯域フィードバックを有する逆レスマルチアーマバンドの高能率強化学習
- Authors: Guojun Xiong, Jian Li,
- Abstract要約: Restless Multi-armed bandits (RMAB)は、シーケンシャルな意思決定問題のモデル化において中心的な役割を果たす。
本稿では,未知の遷移関数と対向報酬を持つ表在的RMABにおける学習課題について考察する。
我々は2つの重要な貢献者による新しい強化学習アルゴリズムを開発した。
- 参考スコア(独自算出の注目度): 11.262167746929332
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Restless multi-armed bandits (RMAB) play a central role in modeling sequential decision making problems under an instantaneous activation constraint that at most B arms can be activated at any decision epoch. Each restless arm is endowed with a state that evolves independently according to a Markov decision process regardless of being activated or not. In this paper, we consider the task of learning in episodic RMAB with unknown transition functions and adversarial rewards, which can change arbitrarily across episodes. Further, we consider a challenging but natural bandit feedback setting that only adversarial rewards of activated arms are revealed to the decision maker (DM). The goal of the DM is to maximize its total adversarial rewards during the learning process while the instantaneous activation constraint must be satisfied in each decision epoch. We develop a novel reinforcement learning algorithm with two key contributors: a novel biased adversarial reward estimator to deal with bandit feedback and unknown transitions, and a low-complexity index policy to satisfy the instantaneous activation constraint. We show $\tilde{\mathcal{O}}(H\sqrt{T})$ regret bound for our algorithm, where $T$ is the number of episodes and $H$ is the episode length. To our best knowledge, this is the first algorithm to ensure $\tilde{\mathcal{O}}(\sqrt{T})$ regret for adversarial RMAB in our considered challenging settings.
- Abstract(参考訳): レストレス・マルチアーム・バンディット(RMAB)は、瞬時アクティベーション制約の下での逐次決定問題のモデル化において中心的な役割を果たす。
各レストアームには、活性化の有無にかかわらずマルコフ決定プロセスに従って独立に進化する状態が与えられる。
本稿では,各エピソードにおいて任意に変化しうる,未知の遷移関数と敵の報酬を持つ表在的RMABにおける学習課題について考察する。
さらに,動作中の腕の対人報酬のみを意思決定者(DM)に開示する,困難だが自然な盗聴フィードバックの設定も検討する。
DMの目的は、学習過程における全対向報酬を最大化することであり、同時に、各決定時代において即時的なアクティベーション制約を満たさなければならない。
本稿では,帯域フィードバックと未知の遷移に対処する新しいバイアス付き対向報酬推定器と,瞬時アクティベーション制約を満たす低複雑さ指標ポリシーの2つの主要な貢献者による新しい強化学習アルゴリズムを開発する。
我々は、我々のアルゴリズムに対して$\tilde{\mathcal{O}}(H\sqrt{T})$ regret boundを示す。
我々の知る限り、このアルゴリズムは、私たちが検討した挑戦的な設定において、RMABの敵に対する後悔を$\tilde{\mathcal{O}}(\sqrt{T})$で保証する最初のアルゴリズムである。
関連論文リスト
- An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints [29.596684377841182]
本研究では、休息状態において、アームの平均報酬が各プルで減少する可能性があるが、そうでなければ変化しない、無限に多くの武器を持つバンディット問題を考察する。
本稿では,ゆがみ報酬に起因するバイアスや分散トレードオフを管理するために,適応的なスライディングウィンドウを備えたUTBを利用するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-04-22T14:11:54Z) - Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳(メタデータ) (2023-05-31T22:09:24Z) - Weighted Tallying Bandits: Overcoming Intractability via Repeated
Exposure Optimality [46.445321251991096]
推薦システムやクラウドソーシングアプリケーションでは、人間の好みや能力はアルゴリズムの最近の行動の関数であることが多い。
我々は、この設定を一般化するWeighted Tallying Bandit (WTB)を導入し、アクションの損失が、前回の$m$のタイムステップで腕が演奏された回数のエンフ和関数であることを要求して、この設定を一般化する。
我々は、$K$アクションと水平線$T$の問題に対して、逐次除去アルゴリズムの簡単な変更は、$O left( sqrtKT + m+)を持つことを示した。
論文 参考訳(メタデータ) (2023-05-04T15:59:43Z) - Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文 参考訳(メタデータ) (2022-04-24T03:10:27Z) - Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。
楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。
我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
論文 参考訳(メタデータ) (2021-10-21T15:25:15Z) - Multi-armed Bandit Requiring Monotone Arm Sequences [0.0]
腕列が単調である必要がある場合の連続武器バンドイット問題について考察する。
未知の目的関数がリプシッツ連続であるとき、後悔は提案アルゴリズムの下で$tilde O(T3/4)$であることを示す。
これは、連続武装バンディット文学における最適レート$tilde O(T2/3)$から逸脱し、単調性要求によってもたらされる学習効率のコストを示す。
論文 参考訳(メタデータ) (2021-06-07T16:53:05Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳(メタデータ) (2021-01-31T16:49:07Z) - Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。
我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。
鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
論文 参考訳(メタデータ) (2021-01-30T21:51:47Z) - Simultaneously Learning Stochastic and Adversarial Episodic MDPs with
Known Transition [38.28925339231888]
我々は,世界最良保証付きの最初のアルゴリズムを開発した。
損失が逆ならば、$mathcalO(log T)$ regretを達成します。
より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
論文 参考訳(メタデータ) (2020-06-10T01:59:34Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳(メタデータ) (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。