論文の概要: Fairness of Exposure in Online Restless Multi-armed Bandits
- arxiv url: http://arxiv.org/abs/2402.06348v1
- Date: Fri, 9 Feb 2024 11:53:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-12 17:05:57.593064
- Title: Fairness of Exposure in Online Restless Multi-armed Bandits
- Title（参考訳）: オンラインrestless multi-armed banditsにおける被曝の公平性
- Authors: Archit Sood, Shweta Jain and Sujit Gujar
- Abstract要約: レストレス・マルチアーム・バンディット(RMAB)は、各アームがマルコフの挙動と遷移を遷移ダイナミクスに従って示すマルチアーム・バンディットを一般化する。
我々は,本アルゴリズムが単一プルの場合,$O(sqrtTln T)$,$T$がエピソードの総数であることを示す。
- 参考スコア（独自算出の注目度）: 8.071147275221973
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Restless multi-armed bandits (RMABs) generalize the multi-armed bandits where
each arm exhibits Markovian behavior and transitions according to their
transition dynamics. Solutions to RMAB exist for both offline and online cases.
However, they do not consider the distribution of pulls among the arms. Studies
have shown that optimal policies lead to unfairness, where some arms are not
exposed enough. Existing works in fairness in RMABs focus heavily on the
offline case, which diminishes their application in real-world scenarios where
the environment is largely unknown. In the online scenario, we propose the
first fair RMAB framework, where each arm receives pulls in proportion to its
merit. We define the merit of an arm as a function of its stationary reward
distribution. We prove that our algorithm achieves sublinear fairness regret in
the single pull case $O(\sqrt{T\ln T})$, with $T$ being the total number of
episodes. Empirically, we show that our algorithm performs well in the
multi-pull scenario as well.
- Abstract（参考訳）: restless multi-armed bandits (rmabs) は、各アームがマルコフの挙動を示し、遷移ダイナミクスに従って遷移するマルチアームのbanditを一般化する。
RMABへのソリューションは、オフラインとオンラインの両方で存在する。
しかし、両腕間の引き根の分布は考慮していない。
研究によると、最適な政策は、一部の腕が十分に露出していない不公平につながる。
rmabsのフェアネスにおける既存の作業は、オフラインのケースに重点を置いている。
オンラインシナリオでは、各アームがそのメリットに比例してプルを受け取る最初の公正なRMABフレームワークを提案する。
我々は、アームの利点を固定報酬分布の関数として定義する。
我々は,本アルゴリズムが単一プルケースである$O(\sqrt{T\ln T})$,$T$がエピソードの総数である場合に,サブ線形公正性を後悔させることを示す。
経験的に,本アルゴリズムはマルチプルシナリオでも良好に動作することを示す。
関連論文リスト
- Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳（メタデータ） (2024-09-09T18:23:07Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Global Rewards in Restless Multi-Armed Bandits [37.918982196934216]
レストレス・マルチアーム・バンディット(RMAB)はマルチアーム・バンディットを拡張し、腕を引っ張って将来の状態に影響を及ぼす。
RMABの成功にもかかわらず、重要な制限の前提は、報酬を武器の合計に分離できることである。
我々は、RMABのグローバル非分離報酬への一般化である、グローバル報酬(RMAB-G)を用いたレスレスマルチアームバンディットを提案する。
論文 参考訳（メタデータ） (2024-06-02T13:13:46Z) - Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints [17.403031677689427]
我々は「長期公正制約」を持つ新しいRMABモデルを導入する。
オンラインRMAB-F設定では、各腕に関連する基礎となるMDPがDMに未知である。
Fair-UCRLは、報酬の後悔と公正性違反の両面において、確率的サブリニア境界を保証することを証明している。
論文 参考訳（メタデータ） (2023-12-16T03:35:56Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳（メタデータ） (2022-03-29T04:58:04Z) - Learning in Restless Bandits under Exogenous Global Markov Process [13.836565669337057]
レスレス・マルチアーム・バンディット(RMAB)問題に対する未知のアームダイナミクスの拡張について検討する。
各グローバル状態の下では、各腕の報酬過程は未知のマルコフの規則に従って進化する。
我々は,後悔を最小限に抑えるために,外因性マルコフ過程(LEMP)に基づく学習法を開発した。
論文 参考訳（メタデータ） (2021-12-17T12:47:30Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - Fair Algorithms for Multi-Agent Multi-Armed Bandits [29.68201160277817]
本稿では,古典的マルチアームバンディット問題のマルチエージェント変種を提案する。
目的は「ベストアーム」を学ばないことであり、実際、各エージェントは別のアームを個人にとって最高のものとみなすことができる。
3つの古典的マルチアームバンディットアルゴリズムのマルチエージェント変種が,サブ線形後悔を実現することを示す。
論文 参考訳（メタデータ） (2020-07-13T21:20:04Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。