論文の概要: The price of unfairness in linear bandits with biased feedback
- arxiv url: http://arxiv.org/abs/2203.09784v1
- Date: Fri, 18 Mar 2022 08:03:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-21 15:56:13.120048
- Title: The price of unfairness in linear bandits with biased feedback
- Title（参考訳）: バイアスドフィードバックを用いたリニアバンディットにおける不公平性の価格
- Authors: Solenne Gaucher (LMO, CELESTE), Alexandra Carpentier, Christophe
Giraud (LMO, CELESTE)
- Abstract要約: 線形帯域フィードバックによる逐次意思決定の問題点について検討する。
その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
- 参考スコア（独自算出の注目度）: 62.25313751895011
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Artificial intelligence is increasingly used in a wide range of decision
making scenarios with higher and higher stakes. At the same time, recent work
has highlighted that these algorithms can be dangerously biased, and that their
results often need to be corrected to avoid leading to unfair decisions. In
this paper, we study the problem of sequential decision making with biased
linear bandit feedback. At each round, a player selects an action described by
a covariate and by a sensitive attribute. She receives a reward corresponding
to the covariates of the action that she has chosen, but only observe a biased
evaluation of this reward, where the bias depends on the sensitive attribute.
To tackle this problem, we design a Fair Phased Elimination algorithm. We
establish an upper bound on its worst-case regret, showing that it is smaller
than C$\kappa$ 1/3 * log(T) 1/3 T 2/3 , where C is a numerical constant and
$\kappa$ * an explicit geometrical constant characterizing the difficulty of
bias estimation. The worst case regret is higher than the dT 1/2 log(T) regret
rate obtained under unbiased feedback. We show that this rate cannot be
improved for all instances : we obtain lower bounds on the worst-case regret
for some sets of actions showing that this rate is tight up to a
sub-logarithmic factor. We also obtain gap-dependent upper bounds on the
regret, and establish matching lower bounds for some problem instance.
Interestingly, the gap-dependent rates reveal the existence of non-trivial
instances where the problem is no more difficult than its unbiased counterpart.
- Abstract（参考訳）: 人工知能は、より高い利害関係を持つ幅広い意思決定シナリオでますます使われています。
同時に、最近の研究は、これらのアルゴリズムは危険に偏りがあり、不公平な決定につながるのを避けるために結果を修正する必要があることを強調している。
本稿では,線形バンディットフィードバックを用いた逐次意思決定の問題について検討する。
各ラウンドで、プレイヤーは共変量と敏感な属性によって記述されたアクションを選択する。
彼女は選択した行動の共変量に対応する報酬を受け取るが、バイアスが敏感な属性に依存するこの報酬に対する偏りのある評価を観察するのみである。
この問題に対処するため、Fair Phased Eliminationアルゴリズムを設計する。
c は数値定数であり、$\kappa$ * 1/3 * log(t) 1/3 t 2/3 はバイアス推定の難しさを特徴付ける明示的な幾何学定数である。
最悪の場合の後悔は、偏りのないフィードバックの下で得られたdT 1/2 log(T)後悔率よりも高い。
このレートはすべてのインスタンスで改善できないことが示されている:我々は、いくつかのアクションセットに対して最悪の場合の後悔の限界を低くし、この割合がサブロガリスミックな要因に密接であることを示す。
また、後悔点上のギャップ依存上界を求め、ある問題事例に対して一致する下界を確立する。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
関連論文リスト
- An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints [29.596684377841182]
本研究では、休息状態において、アームの平均報酬が各プルで減少する可能性があるが、そうでなければ変化しない、無限に多くの武器を持つバンディット問題を考察する。
本稿では,ゆがみ報酬に起因するバイアスや分散トレードオフを管理するために,適応的なスライディングウィンドウを備えたUTBを利用するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-22T14:11:54Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす
本稿では,本問題の領域内モデルについて考察する。-文脈的デュエルバンディットと敵対的フィードバックを併用し,真の嗜好ラベルを敵によって反転させることができる。
本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(アルゴ)を提案する。
論文 参考訳（メタデータ） (2024-04-16T17:59:55Z) - Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs [32.29254118429081]
我々は,帯域幅フィードバックの下での最適誤りが,全情報ケースの最適誤りよりも少なくとも$O(k)$倍高いことを示す。
また、ランダム化学習者と決定論的学習者の間のギャップに対して、$tildeTheta(k)$のほぼ最適な境界を示す。
論文 参考訳（メタデータ） (2024-02-12T07:20:05Z) - 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) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳（メタデータ） (2023-03-15T17:59:27Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Minimax Regret for Stochastic Shortest Path with Adversarial Costs and
Known Transition [37.6975819766632]
我々は、敵対コストと既知の移行で最短経路問題を研究します。
ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
論文 参考訳（メタデータ） (2020-12-07T20:55:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。