論文の概要: Optimistic Whittle Index Policy: Online Learning for Restless Bandits
- arxiv url: http://arxiv.org/abs/2205.15372v1
- Date: Mon, 30 May 2022 18:32:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-02 09:52:11.567477
- Title: Optimistic Whittle Index Policy: Online Learning for Restless Bandits
- Title(参考訳): Optimistic Whittle Index Policy: レストバンドのためのオンライン学習
- Authors: Kai Wang, Lily Xu, Aparna Taneja, Milind Tambe
- Abstract要約: 遷移力学を学習するためのWhittleインデックスポリシーに基づく,最初のオンライン学習アルゴリズムを提案する。
我々のアルゴリズムUCWhittleは、RMABを未知の遷移で解くために、サブ線形$O(sqrtT log T)$の頻繁な後悔を実現する。
- 参考スコア(独自算出の注目度): 31.312043984489666
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Restless multi-armed bandits (RMABs) extend multi-armed bandits to allow for
stateful arms, where the state of each arm evolves restlessly with different
transitions depending on whether that arm is pulled. However, solving RMABs
requires information on transition dynamics, which is often not available
upfront. To plan in RMAB settings with unknown transitions, we propose the
first online learning algorithm based on the Whittle index policy, using an
upper confidence bound (UCB) approach to learn transition dynamics.
Specifically, we formulate a bilinear program to compute the optimistic Whittle
index from the confidence bounds in transition dynamics. Our algorithm,
UCWhittle, achieves sublinear $O(\sqrt{T \log T})$ frequentist regret to solve
RMABs with unknown transitions. Empirically, we demonstrate that UCWhittle
leverages the structure of RMABs and the Whittle index policy solution to
achieve better performance than existing online learning baselines across three
domains, including on real-world maternal and childcare data aimed at reducing
maternal mortality.
- Abstract(参考訳): レストレス・マルチアーム・バンディット(RMAB)は、多腕のバンディットを拡張してステートフルアームを可能にし、各アームの状態は、腕を引っ張るかどうかによって異なる遷移で、レストレスで進化する。
しかし、RMABの解決にはトランジッションダイナミクスに関する情報が必要である。
未知の遷移を伴うrmab設定を計画するために, 遷移ダイナミクスを学習するためのuper confidence bound (ucb) アプローチを用いて, whittle index policyに基づく最初のオンライン学習アルゴリズムを提案する。
具体的には、遷移ダイナミクスの信頼度境界から楽観的なウィットル指数を計算するために双線型プログラムを定式化する。
我々のアルゴリズムUCWhittleは、RMABを未知の遷移で解くために、サブ線形$O(\sqrt{T \log T})$の頻繁な後悔を実現する。
経験的に、ucwhittleは、rmabsとwhitle index policy solutionの構造を利用して、3つのドメインにまたがる既存のオンライン学習ベースラインよりも優れたパフォーマンスを達成することを実証している。
関連論文リスト
- A Bayesian Approach to Online Learning for Contextual Restless Bandits
with Applications to Public Health [39.513593558052314]
本稿では,RMABのオンライン強化学習手法としてBayesian Learning for Contextual RMABs(BCoR)を提案する。
BCoRは, 実験条件下での既存手法に比べて, かなり高い有限サンプル性能を実現することを示す。
論文 参考訳(メタデータ) (2024-02-07T15:11:37Z) - Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。
我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
論文 参考訳(メタデータ) (2023-07-05T13:52:10Z) - Meta-Learning Adversarial Bandits [49.094361442409785]
本研究の目的は,複数のタスクにまたがる帯域幅フィードバックを用いてオンライン学習を学習し,タスク間の平均性能を改善することである。
敵対的設定を最初に対象とするメタアルゴリズムとして,マルチアーム・バンディット(MAB)とバンディット・最適化(BLO)の2つの重要なケースに対して,特定の保証を設定するメタアルゴリズムを設計する。
我々の保証は、非正規化されたフォローザリーダーと乗法重みを組み合わせることで、オンラインで非滑らかで非Bシーケンスを学ぶのに十分であることを示すことに依存しています。
論文 参考訳(メタデータ) (2022-05-27T17:40:32Z) - Scalable Decision-Focused Learning in Restless Multi-Armed Bandits with
Application to Maternal and Child Health [36.442133189056136]
本稿では、未知のアーム遷移ダイナミクスを持つが、既知の相関アーム特徴を持つ、レスレスマルチアーム・バンディット(RMAB)問題について検討する。
目標は、WhittleインデックスポリシーがRMAB問題を予測トランジションを用いて解決する、与えられた特徴の遷移ダイナミクスを予測するモデルを学ぶことである。
そこで本研究では,Whittle指数解の品質を最大化するために,予測モデルを直接訓練するRMABにおける意思決定型学習手法を提案する。
論文 参考訳(メタデータ) (2022-02-02T08:36:10Z) - Robust Restless Bandits: Tackling Interval Uncertainty with Deep
Reinforcement Learning [31.515757763077065]
我々は、レスレス・マルチアーム・バンディット(RMAB)の一般化であるRobust Restless Banditsを紹介する。
遷移が区間不確実性によって与えられる場合、最小限の後悔目標に対する解を開発する。
RMABPPOはRMABを解くための新しい深層強化学習アルゴリズムである。
論文 参考訳(メタデータ) (2021-07-04T17:21:26Z) - 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) - Semi-Supervised Learning with Variational Bayesian Inference and Maximum
Uncertainty Regularization [62.21716612888669]
半教師付き学習(SSL)を改善するための2つの一般的な方法を提案する。
第一に、重量摂動(WP)を既存のCR(Consistency regularization)ベースの手法に統合する。
第2の手法は「最大不確実性正規化(MUR)」と呼ばれる新しい整合性損失を提案する。
論文 参考訳(メタデータ) (2020-12-03T09:49:35Z) - Restless-UCB, an Efficient and Low-complexity Algorithm for Online
Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。
本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文 参考訳(メタデータ) (2020-11-05T05:16:04Z) - Solving Sparse Linear Inverse Problems in Communication Systems: A Deep
Learning Approach With Adaptive Depth [51.40441097625201]
疎信号回復問題に対するエンドツーエンドの訓練可能なディープラーニングアーキテクチャを提案する。
提案手法は,出力するレイヤ数を学習し,各タスクのネットワーク深さを推論フェーズで動的に調整する。
論文 参考訳(メタデータ) (2020-10-29T06:32:53Z) - Robust Inverse Reinforcement Learning under Transition Dynamics Mismatch [60.23815709215807]
本研究では,逆強化学習(IRL)問題について,専門家と学習者間の遷移力学ミスマッチの下で検討する。
本稿では,このミスマッチを支援するための基本手法として,ロバストなMCE IRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-07-02T14:57:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。