論文の概要: Improved Regret Bounds for Online Fair Division with Bandit Learning

• arxiv url: http://arxiv.org/abs/2501.07022v1
• Date: Mon, 13 Jan 2025 02:48:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 14:21:09.351914
• Title: Improved Regret Bounds for Online Fair Division with Bandit Learning
• Title（参考訳）: バンディット学習によるオンラインフェアディビジョンにおけるレグレット境界の改善
• Authors: Benjamin Schiffer, Shirley Zhang,
• Abstract要約: アイテムの種類が有限であればオンラインフェアディビジョンを学習し、そのアイテムのプレイヤー値は未知の方法で分布からランダムに描画される。 この設定では、分割不可能なアイテムの列がランダムなオンラインプロセスに従って到着し、各アイテムは1人のプレイヤーに割り当てられなければならない。 高い確率で比例制約満足度を保証し、$tildeO(sqrtT)$ regretを達成できることが示される。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We study online fair division when there are a finite number of item types and the player values for the items are drawn randomly from distributions with unknown means. In this setting, a sequence of indivisible items arrives according to a random online process, and each item must be allocated to a single player. The goal is to maximize expected social welfare while maintaining that the allocation satisfies proportionality in expectation. When player values are normalized, we show that it is possible to with high probability guarantee proportionality constraint satisfaction and achieve $\tilde{O}(\sqrt{T})$ regret. To achieve this result, we present an upper confidence bound (UCB) algorithm that uses two rounds of linear optimization. This algorithm highlights fundamental aspects of proportionality constraints that allow for a UCB algorithm despite the presence of many (potentially tight) constraints. This result improves upon the previous best regret rate of $\tilde{O}(T^{2/3})$.
• Abstract（参考訳）: アイテムの種類が有限であればオンラインフェアディビジョンを学習し、そのアイテムのプレイヤー値は未知の方法で分布からランダムに描画される。 この設定では、分割不可能なアイテムの列がランダムなオンラインプロセスに従って到着し、各アイテムは1人のプレイヤーに割り当てられなければならない。 目標は、配分が期待の比例性を満たすことを保ちながら、期待される社会福祉を最大化することである。 プレイヤーの値が正規化されると、高い確率で比例制約を満たすことができ、$\tilde{O}(\sqrt{T})$ regretを達成できることを示す。 この結果を得るために,2ラウンドの線形最適化を用いた上信頼境界(UCB)アルゴリズムを提案する。 このアルゴリズムは、多くの(潜在的に厳密な)制約があるにもかかわらず、UCBアルゴリズムを可能にする比例制約の基本的な側面を強調している。 この結果は、以前の最高の後悔率である$\tilde{O}(T^{2/3})$を改善する。

関連論文リスト

• Honor Among Bandits: No-Regret Learning for Online Fair Division [20.38824614301761]
  本研究では, 商品の種類が有限であり, プレイヤーの値が未知の方法で分布から引き出される場合, プレイヤーに対する不特定商品のオンライン公平分割の問題点を考察する。 我々の主な成果は、公正な制約を維持しながら、$tildeO(T2/3)の後悔を達成できる探索列コミットアルゴリズムの設計である。
  論文  参考訳（メタデータ） (2024-07-01T20:44:52Z)
• No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization [26.415300249303748]
  本研究は, 一次アルゴリズムと双対アルゴリズムを弱適応化させることにより, 制約のサブ線形違反を回避可能であることを示す。 最初のケースでは、アルゴリズムがサブ線形後悔を保証することを示し、後者の場合、厳密な競合比を$rho/(1+rho)$とする。 この結果から,線形制約付き文脈帯域問題に対する新たな結果が得られる。
  論文  参考訳（メタデータ） (2024-05-10T16:22:33Z)
• 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)
• Contextual Bandits with Stage-wise Constraints [46.412612374393895]
  段階的制約(各ラウンドにおける制約)の存在下での文脈的包帯について検討する。 本稿では,この問題に対する高信頼度有界アルゴリズムを提案し,それに対するT$ラウンドの後悔を証明した。
  論文  参考訳（メタデータ） (2024-01-15T23:58:21Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。 我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-21T16:43:03Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Differentiable Linear Bandit Algorithm [6.849358422233866]
  アッパー信頼境界は、線形多腕バンディット問題の最も一般的な方法である。 勾配上昇による信頼度を学習できる勾配推定器を導入する。 提案アルゴリズムは,腕の特徴の次元を$d$で,信頼度を$hatbeta$で学習したサイズを$tildemathcalO(hatbetasqrtdT)$上限とする。
  論文  参考訳（メタデータ） (2020-06-04T16:43:55Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。