論文の概要: 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$がエピソードの総数である場合に,サブ線形公正性を後悔させることを示す。
経験的に,本アルゴリズムはマルチプルシナリオでも良好に動作することを示す。
関連論文リスト
- 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) - Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。
評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
論文 参考訳(メタデータ) (2021-12-13T09:48:54Z) - 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) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳(メタデータ) (2021-02-15T19:10:52Z) - 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) - Sequential Monte Carlo Bandits [1.9205272414658485]
我々は、連続モンテカルロ法(SMC)を用いることで、ベイジアン多重武装バンディット(MAB)アルゴリズムを元の設定を超えて拡張する。
MABは、長期的な支払いを最大化するポリシーを学ぶことを目標とするシーケンシャルな意思決定問題である。
本稿では,線形力学系を用いて時間力学をモデル化した非定常帯域について述べる。
論文 参考訳(メタデータ) (2018-08-08T20:40:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。