論文の概要: A Regret bound for Non-stationary Multi-Armed Bandits with Fairness
Constraints
- arxiv url: http://arxiv.org/abs/2012.13380v1
- Date: Thu, 24 Dec 2020 18:12:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-25 08:25:07.419304
- Title: A Regret bound for Non-stationary Multi-Armed Bandits with Fairness
Constraints
- Title（参考訳）: フェアネス制約付き非定常多関節帯域に対するレグレトバウンド
- Authors: Shaarad A. R and Ambedkar Dukkipati
- Abstract要約: 我々は,緩やかに変化する$k$-armed bandit問題を解くために,fair upper confidenceと呼ばれる新しいアルゴリズムとexploring fair-ucbeを提案する。
非定常ケースにおけるアルゴリズムの性能は,その定常ケースに近づくとゼロになりがちであることを示す。
- 参考スコア（独自算出の注目度）: 7.716156977428555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The multi-armed bandits' framework is the most common platform to study
strategies for sequential decision-making problems. Recently, the notion of
fairness has attracted a lot of attention in the machine learning community.
One can impose the fairness condition that at any given point of time, even
during the learning phase, a poorly performing candidate should not be
preferred over a better candidate. This fairness constraint is known to be one
of the most stringent and has been studied in the stochastic multi-armed
bandits' framework in a stationary setting for which regret bounds have been
established. The main aim of this paper is to study this problem in a
non-stationary setting. We present a new algorithm called Fair Upper Confidence
Bound with Exploration Fair-UCBe algorithm for solving a slowly varying
stochastic $k$-armed bandit problem. With this we present two results: (i)
Fair-UCBe indeed satisfies the above mentioned fairness condition, and (ii) it
achieves a regret bound of $O\left(k^{\frac{3}{2}} T^{1 - \frac{\alpha}{2}}
\sqrt{\log T}\right)$, for some suitable $\alpha \in (0, 1)$, where $T$ is the
time horizon. This is the first fair algorithm with a sublinear regret bound
applicable to non-stationary bandits to the best of our knowledge. We show that
the performance of our algorithm in the non-stationary case approaches that of
its stationary counterpart as the variation in the environment tends to zero.
- Abstract（参考訳）: マルチアームバンディットのフレームワークは、シーケンシャルな意思決定問題の戦略を研究するための最も一般的なプラットフォームである。
近年、公平性の概念が機械学習コミュニティで注目を集めている。
任意の時点で、たとえ学習段階であっても、成績の悪い候補者がより良い候補者よりも好まれるべきでないという公平な条件を課すことができる。
この公正性制約は最も厳密な1つとして知られており、後悔の限界が確立された定常的な環境で確率的マルチアームバンドの枠組みで研究されている。
本論文の主な目的は,非定常環境でこの問題を研究することである。
本稿では,緩やかに変化する確率的k$-armed bandit問題を解くための探索的fair-ucbeアルゴリズムと結びついた,fair upper confidenceと呼ばれる新しいアルゴリズムを提案する。
i)fair-ucbeは、上記のフェアネス条件を実際に満たしており、(ii)$t$が時平線であるいくつかの適切な$\alpha \in (0, 1)$に対して、$o\left(k^{\frac{3}{2}} t^{1 - \frac{\alpha}{2}} \sqrt{\log t}\right)$となる。
これは私たちの知識を最大限に活用するために、非定常帯域幅に適用できるサブ線形後悔を持つ最初の公正アルゴリズムである。
非定常の場合におけるアルゴリズムの性能は,環境の変動がゼロになるにつれて定常値に近い値に近づくことが示された。
関連論文リスト
- Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。
われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。
我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
論文 参考訳（メタデータ） (2024-04-09T04:45:18Z) - 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) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Non-Stationary Dueling Bandits [8.298716599039501]
我々は、非定常デュエルバンディット問題をK$アームで研究し、タイムホライズメント$T$は、固定セグメント$M$からなる。
蓄積した後悔を最小限に抑えるため、学習者は各定常セグメントのコンドルチェットの勝者をできるだけ頻繁に選ぶ必要がある。
我々は、M$やT$の知識を必要とせず、非定常ケースに対する後悔の意を示す。
論文 参考訳（メタデータ） (2022-02-02T09:57:35Z) - Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits
with Super Heavy-Tailed Payoffs [27.636407641546914]
実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。
非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
論文 参考訳（メタデータ） (2021-10-26T17:30:44Z) - On Slowly-varying Non-stationary Bandits [25.305949034527202]
我々は、ゆっくりと変化する性質を持つ非定常包帯の動的後悔を考察する。
我々は、ゆっくりと変化する非定常帯域に対して、最初のインスタンス依存後悔上限を確立する。
我々のアルゴリズムは基本的にミニマックス最適であることを示す。
論文 参考訳（メタデータ） (2021-10-25T12:56:19Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳（メタデータ） (2020-12-24T05:36:29Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms [10.662105162882526]
本研究は,Emphmany-armed regimeにおける$k$-armed bandit問題について考察する。
以上の結果から,多腕の環境下での強欲なアルゴリズムには,新たなエフェフリー探索法が有用であることが示唆された。
論文 参考訳（メタデータ） (2020-02-24T08:59:34Z) - Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。
提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-20T06:36:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。