論文の概要: Global Rewards in Restless Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2406.00738v2
- Date: Fri, 7 Jun 2024 20:38:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-11 23:15:47.906675
- Title: Global Rewards in Restless Multi-Armed Bandits
- Title(参考訳): レストレス・マルチアーマッドバンドにおけるグローバル・リワード
- Authors: Naveen Raman, Zheyuan Ryan Shi, Fei Fang,
- Abstract要約: レストレス・マルチアーム・バンディット(RMAB)はマルチアーム・バンディットを拡張し、腕を引っ張って将来の状態に影響を及ぼす。
RMABの成功にもかかわらず、重要な制限の前提は、報酬を武器の合計に分離できることである。
我々は、RMABのグローバル非分離報酬への一般化である、グローバル報酬(RMAB-G)を用いたレスレスマルチアームバンディットを提案する。
- 参考スコア(独自算出の注目度): 37.918982196934216
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Restless multi-armed bandits (RMAB) extend multi-armed bandits so pulling an arm impacts future states. Despite the success of RMABs, a key limiting assumption is the separability of rewards into a sum across arms. We address this deficiency by proposing restless-multi-armed bandit with global rewards (RMAB-G), a generalization of RMABs to global non-separable rewards. To solve RMAB-G, we develop the Linear- and Shapley-Whittle indices, which extend Whittle indices from RMABs to RMAB-Gs. We prove approximation bounds but also point out how these indices could fail when reward functions are highly non-linear. To overcome this, we propose two sets of adaptive policies: the first computes indices iteratively, and the second combines indices with Monte-Carlo Tree Search (MCTS). Empirically, we demonstrate that our proposed policies outperform baselines and index-based policies with synthetic data and real-world data from food rescue.
- Abstract(参考訳): レストレス・マルチアーム・バンディット(RMAB)はマルチアーム・バンディットを拡張し、腕を引っ張って将来の状態に影響を及ぼす。
RMABの成功にもかかわらず、重要な制限の前提は、報酬を武器の合計に分離できることである。
本研究は, RMABのグローバルな非分離型報酬への一般化である, RMAB-Gを用いたレスレスマルチアームバンディットの提案により, この欠陥に対処する。
RMAB-Gを解くために,RMABからRMAB-GまでWhittleインデックスを拡張可能な線形およびシェープWhittleインデックスを開発した。
近似境界を証明するとともに、報酬関数が非線形であるときにこれらの指標がいかに失敗するかを指摘する。
これを解決するために、第1の計算指標を反復的に、第2の計算指標をモンテカルロ木探索(MCTS)と組み合わせた2つの適応ポリシーを提案する。
実験により, 提案した政策は, 食品の回収から得られる合成データと実世界のデータを用いて, ベースラインやインデックスベースの政策よりも優れていることを示した。
関連論文リスト
- Fairness of Exposure in Online Restless Multi-armed Bandits [8.071147275221973]
レストレス・マルチアーム・バンディット(RMAB)は、各アームがマルコフの挙動と遷移を遷移ダイナミクスに従って示すマルチアーム・バンディットを一般化する。
我々は,本アルゴリズムが単一プルの場合,$O(sqrtTln T)$,$T$がエピソードの総数であることを示す。
論文 参考訳(メタデータ) (2024-02-09T11:53:27Z) - Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints [17.403031677689427]
我々は「長期公正制約」を持つ新しいRMABモデルを導入する。
オンラインRMAB-F設定では、各腕に関連する基礎となるMDPがDMに未知である。
Fair-UCRLは、報酬の後悔と公正性違反の両面において、確率的サブリニア境界を保証することを証明している。
論文 参考訳(メタデータ) (2023-12-16T03:35:56Z) - 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) - Limited Resource Allocation in a Non-Markovian World: The Case of
Maternal and Child Healthcare [27.812174610119452]
低リソース環境におけるスケジューリング介入の問題点を考察し,順応性やエンゲージメントを高めることを目的とする。
過去の研究は、この問題に対する数種類のRestless Multi-armed Bandit (RMAB) ベースのソリューションの開発に成功している。
我々のパートナーであるNGO ARMMAN の母体健康意識プログラムにおける実世界データに対する Markov の仮定から大きく逸脱した。
一般化された非マルコフ的RMAB設定に取り組むために、(i)各参加者の軌跡を時系列としてモデル化し、(ii)時系列予測モデルのパワーを利用して将来の状態を予測し、(iii)時間を提案する。
論文 参考訳(メタデータ) (2023-05-22T02:26:29Z) - Contextual bandits with concave rewards, and an application to fair
ranking [108.48223948875685]
CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。
我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。
推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
論文 参考訳(メタデータ) (2022-10-18T16:11:55Z) - Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When
Partial Feedback Counts [53.579515853222986]
時間分割リワード(TP-MAB)を用いたマルチアーメッド・バンディット(Multi-Armed Bandit)について検討する。
この設定は、プル後の有限時間スパン上で報酬が拡張されるケースに対する遅延フィードバックバンディットの自然な拡張である。
本稿では,TP-UCB-FRとTP-UCB-EWの2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-06-01T15:56:59Z) - Robust Restless Bandits: Tackling Interval Uncertainty with Deep
Reinforcement Learning [31.515757763077065]
我々は、レスレス・マルチアーム・バンディット(RMAB)の一般化であるRobust Restless Banditsを紹介する。
遷移が区間不確実性によって与えられる場合、最小限の後悔目標に対する解を開発する。
RMABPPOはRMABを解くための新しい深層強化学習アルゴリズムである。
論文 参考訳(メタデータ) (2021-07-04T17:21:26Z) - DORB: Dynamically Optimizing Multiple Rewards with Bandits [101.68525259222164]
政策に基づく強化学習は、言語生成タスクにおいて、微分不可能な評価指標を最適化するための有望なアプローチであることが証明されている。
We use the Exp3 algorithm for bandit and formulate two approach for bandit rewards: (1) Single Multi-reward Bandit (SM-Bandit), (2) Hierarchical Multi-reward Bandit (HM-Bandit)
我々は,2つの重要なNLGタスクにおいて,様々な自動計測と人的評価を通じて,我々のアプローチの有効性を実証的に示す。
論文 参考訳(メタデータ) (2020-11-15T21:57:47Z) - Simulation Based Algorithms for Markov Decision Processes and
Multi-Action Restless Bandits [0.0]
我々は,多次元状態空間と多動作バンドイットモデルを備えたレスレスマルチアームバンドイット(RMAB)を考える。
まず、標準的なインデックス可能なRMAB(2アクションモデル)を分析し、インデックスベースのポリシーアプローチについて議論する。
モンテカルロロールアウトポリシを用いた近似インデックスアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-07-25T13:50:08Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳(メタデータ) (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。