論文の概要: Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee
for Improving Bandits
- arxiv url: http://arxiv.org/abs/2208.09254v1
- Date: Fri, 19 Aug 2022 10:23:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-22 16:42:05.583874
- Title: Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee
for Improving Bandits
- Title（参考訳）: 報酬を最大化しながら格差を緩和する:バンド改善のためのタイトな保証
- Authors: Vishakha Patil, Vineet Nair, Ganesh Ghalme, Arindam Khan
- Abstract要約: 腕から得られる報酬が、受信したプル数に応じて増加するIMAB問題について検討する。
我々の主な貢献は、最良の累積報酬を達成するIMAB問題に対する任意のアルゴリズムである。
- 参考スコア（独自算出の注目度）: 6.537940428724029
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the Improving Multi-Armed Bandit (IMAB) problem, where the reward
obtained from an arm increases with the number of pulls it receives. This model
provides an elegant abstraction for many real-world problems in domains such as
education and employment, where decisions about the distribution of
opportunities can affect the future capabilities of communities and the
disparity between them. A decision-maker in such settings must consider the
impact of her decisions on future rewards in addition to the standard objective
of maximizing her cumulative reward at any time. In many of these applications,
the time horizon is unknown to the decision-maker beforehand, which motivates
the study of the IMAB problem in the technically more challenging
horizon-unaware setting. We study the tension that arises between two seemingly
conflicting objectives in the horizon-unaware setting: a) maximizing the
cumulative reward at any time based on current rewards of the arms, and b)
ensuring that arms with better long-term rewards get sufficient opportunities
even if they initially have low rewards. We show that, surprisingly, the two
objectives are aligned with each other in this setting. Our main contribution
is an anytime algorithm for the IMAB problem that achieves the best possible
cumulative reward while ensuring that the arms reach their true potential given
sufficient time. Our algorithm mitigates the initial disparity due to lack of
opportunity and continues pulling an arm till it stops improving. We prove the
optimality of our algorithm by showing that a) any algorithm for the IMAB
problem, no matter how utilitarian, must suffer $\Omega(T)$ policy regret and
$\Omega(k)$ competitive ratio with respect to the optimal offline policy, and
b) the competitive ratio of our algorithm is $O(k)$.
- Abstract（参考訳）: 腕から得られる報酬が、受信したプル数に応じて増加するIMAB問題について検討する。
このモデルは、機会の分配に関する決定がコミュニティの将来的能力とそれら間の格差に影響を及ぼすことができる教育や雇用といった領域における多くの現実的な問題に対して、エレガントな抽象化を提供する。
このような設定の意思決定者は、いつでも累積報酬を最大化する標準的な目的に加えて、将来の報酬に対する彼女の決定の影響を考慮する必要がある。
これらの応用の多くにおいて、時間軸は意思決定者には事前に不明であり、技術的に困難な地平線認識環境におけるイマーブ問題の研究の動機となっている。
地平線を意識しない2つの目的の間に生じる緊張について検討する。
a) 腕の現在の報酬に基づいて,いつでも累積報酬を最大化すること,及び
b) 早期に報酬が少なくても、長期報酬が良好な武器が十分な機会を得られること。
驚くべきことに、この2つの目標は、この設定で互いに一致していることを示します。
我々の主な貢献は、腕が十分な時間に真のポテンシャルに達することを保証しながら、可能な限りの累積報酬を達成するIMAB問題に対する任意のアルゴリズムである。
我々のアルゴリズムは、機会の欠如による初期格差を緩和し、改善が止まるまで腕を引っ張る。
私たちはそれを示してアルゴリズムの最適性を証明する。
a) IMAB問題のアルゴリズムは、どのような実用性があっても、最適のオフラインポリシーに関して、ポリシー後悔の$\Omega(T)と$\Omega(k)の競争比率を被らなければならない。
b)アルゴリズムの競合比は$O(k)$である。
関連論文リスト
- Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。
UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
論文 参考訳（メタデータ） (2024-10-08T09:49:47Z) - Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits
with Strategic Agents [57.627352949446625]
マルチアームバンディット問題の変種を考察する。
具体的には、武器は、報酬を改善したり、吸収したりできる戦略的なエージェントである。
我々は、プロパティの集合を満たすMABアルゴリズムのクラスを特定し、それらが平衡におけるトップレベルのパフォーマンスを刺激するメカニズムをもたらすことを示す。
論文 参考訳（メタデータ） (2023-12-13T06:54:49Z) - Bandits Meet Mechanism Design to Combat Clickbait in Online
Recommendation [50.469872635246176]
我々は,マルチアームバンディット問題の戦略的変種について検討し,これを戦略的クリックバンディット(Click-bandit)と呼ぶ。
このモデルは、推奨項目の選択がクリックスルー率とクリック後の報酬の両方に依存するオンラインレコメンデーションのアプリケーションによって動機付けられている。
論文 参考訳（メタデータ） (2023-11-27T09:19:01Z) - Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals [0.9831489366502302]
予算的マルチアーマッド・バンドイット(MAB)問題について検討し、プレイヤーが期待できない報酬とコストでK$アームから選択する。
非対称な信頼区間を用いた新しいアッパー信頼境界(UCB)サンプリングポリシーである$omega$-UCBを提案する。
これらの間隔は、サンプル平均とランダム変数の境界との間の距離でスケールし、報酬コスト比をより正確かつ厳密に推定する。
論文 参考訳（メタデータ） (2023-06-12T12:35:16Z) - Achieving the Pareto Frontier of Regret Minimization and Best Arm
Identification in Multi-Armed Bandits [91.8283876874947]
本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。
i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。
また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-10-16T17:52:32Z) - Addressing the Long-term Impact of ML Decisions via Policy Regret [49.92903850297013]
意思決定者が腕を引っ張るたびに、各腕からの報酬が進化する状況について検討する。
我々は、許容可能な機会の逐次配分は、成長の可能性を考慮に入れなければならないと論じている。
十分に長い時間的地平線に対して、確実にサブ線形ポリシーを後悔するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-02T17:38:10Z) - Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous
Feedback [32.62857394584907]
複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。
本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-13T12:25:41Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳（メタデータ） (2020-08-10T08:30:52Z) - A Farewell to Arms: Sequential Reward Maximization on a Budget with a
Giving Up Option [5.1629297054995265]
エージェントが一度にひとつのアクションを採り、各アクションが時間的範囲を持つような、シーケンシャルな意思決定問題を考える。
我々は、対数的、問題依存的後悔境界を確立する上で、高い信頼度に基づくアルゴリズム(WAIT-UCB)を導入する。
論文 参考訳（メタデータ） (2020-03-06T22:16:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。