論文の概要: Honor Among Bandits: No-Regret Learning for Online Fair Division
- arxiv url: http://arxiv.org/abs/2407.01795v2
- Date: Sat, 17 Aug 2024 01:53:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-21 02:18:56.994705
- Title: Honor Among Bandits: No-Regret Learning for Online Fair Division
- Title（参考訳）: 参加者の名誉 - オンラインフェアディビジョンのためのNo-Regret Learning
- Authors: Ariel D. Procaccia, Benjamin Schiffer, Shirley Zhang,
- Abstract要約: 本研究では, 商品の種類が有限であり, プレイヤーの値が未知の方法で分布から引き出される場合, プレイヤーに対する不特定商品のオンライン公平分割の問題点を考察する。
我々の主な成果は、公正な制約を維持しながら、$tildeO(T2/3)の後悔を達成できる探索列コミットアルゴリズムの設計である。
- 参考スコア（独自算出の注目度）: 20.38824614301761
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of online fair division of indivisible goods to players when there are a finite number of types of goods and player values are drawn from distributions with unknown means. Our goal is to maximize social welfare subject to allocating the goods fairly in expectation. When a player's value for an item is unknown at the time of allocation, we show that this problem reduces to a variant of (stochastic) multi-armed bandits, where there exists an arm for each player's value for each type of good. At each time step, we choose a distribution over arms which determines how the next item is allocated. We consider two sets of fairness constraints for this problem: envy-freeness in expectation and proportionality in expectation. Our main result is the design of an explore-then-commit algorithm that achieves $\tilde{O}(T^{2/3})$ regret while maintaining either fairness constraint. This result relies on unique properties fundamental to fair-division constraints that allow faster rates of learning, despite the restricted action space. We also prove a lower bound of $\tilde{\Omega}(T^{2/3})$ regret for our setting, showing that our results are tight.
- Abstract（参考訳）: 本研究では, 商品の種類が有限であり, プレイヤーの値が未知の方法で分布から引き出される場合, プレイヤーに対する不特定商品のオンライン公平分割の問題点を考察する。
我々の目標は、期待通りに商品を配分する社会福祉を最大化することです。
割り当て時にアイテムに対するプレイヤーの値が不明な場合、この問題は、各プレイヤーの商品に対して、各プレイヤーの値にアームが存在するような、(確率的な)マルチアームバンディットの変種に還元されることが示される。
各ステップで、次のアイテムをどのように割り当てるかを決定するアーム上の分布を選択します。
この問題に対する公平性制約の2つのセットを考察する: 期待の自由度と期待の比例性である。
我々の主な成果は、公正さの制約を維持しながら、$\tilde{O}(T^{2/3})$ regret を達成する探索-then-commitアルゴリズムの設計である。
この結果は、制限されたアクション空間にもかかわらず、学習の速度を速くする公平な分割の制約に基本となる固有の性質に依存している。
我々はまた、我々の設定に後悔する$\tilde{\Omega}(T^{2/3})の低い境界を証明し、その結果がきついことを示す。
関連論文リスト
- Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。
本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文 参考訳（メタデータ） (2024-09-09T18:23:07Z) - Imprecise Multi-Armed Bandits [0.0]
そこで本研究では,各アームが,結果空間上の固定された未知の干潟と結びついている,新しいマルチアーム・バンディット・フレームワークを提案する。
次に、これらのクレダル集合によって定義される下述の前提に対応する後悔の概念を定義する。
論文 参考訳（メタデータ） (2024-05-09T10:58:40Z) - Trading-off price for data quality to achieve fair online allocation [25.154957931903525]
オンラインアロケーションの問題は、長期的公正なペナルティに該当すると考えられる。
両問題を共同で解き,$mathcalO(sqrtT)$で有界な後悔を示すアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-23T11:09:43Z) - Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳（メタデータ） (2023-05-31T22:09:24Z) - The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。
その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文 参考訳（メタデータ） (2022-03-18T08:03:20Z) - Bandit problems with fidelity rewards [7.154621689269006]
フィデリティ・バンディット問題(英: fidelity bandits problem)とは、過去にプレイヤーがその腕に「ロヤル」したかによって、各腕の報酬がフィデリティ・報酬によって増強されるK$アームのバンディット問題の変種である。
忠誠ポイントモデルでは、余分な報酬の量は、これまで腕が演奏された回数に依存する。
サブスクリプションモデルでは、追加の報酬は腕の連続的な引き分けの数に依存する。
論文 参考訳（メタデータ） (2021-11-25T11:09:43Z) - 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) - Multitask Bandit Learning Through Heterogeneous Feedback Aggregation [35.923544685900055]
我々は,この問題を,一組のプレイヤーが一組のアームと同時に相互作用する,$epsilon$-multi-player multi-armed bandit問題として定式化する。
我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼な有界アルゴリズム、RobostAgg$(epsilon)$を開発する。
論文 参考訳（メタデータ） (2020-10-29T07:13:28Z) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z) - Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。
最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
論文 参考訳（メタデータ） (2020-02-13T08:53:43Z) - Selfish Robustness and Equilibria in Multi-Player Bandits [25.67398941667429]
ゲームでは、複数のプレイヤーが同時に腕を引いて、同じ腕を同時に引っ張る場合、0の報酬で衝突する。
プレイヤーが集団報酬を最大化する協力的ケースは、主に考慮されてきたが、悪意のあるプレイヤーにとっては非常に重要かつ困難な問題である。
代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
論文 参考訳（メタデータ） (2020-02-04T09:50:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。