論文の概要: Bandit Max-Min Fair Allocation

• arxiv url: http://arxiv.org/abs/2505.05169v1
• Date: Thu, 08 May 2025 12:09:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-09 21:43:49.869048
• Title: Bandit Max-Min Fair Allocation
• Title（参考訳）: Bandit Max-Min Fair Allocation
• Authors: Tsubasa Harada, Shinji Ito, Hanna Sumita,
• Abstract要約: 本稿では,BMMFA問題と呼ばれる新たな意思決定問題について検討する。 この問題の目標は、加法的評価を持つエージェント間での最小効用を最大化することである。 この問題の1つの重要な特徴は、各アイテムに対する各エージェントのバリュエーションが半帯域フィードバックによってのみ観察できることである。
• 参考スコア（独自算出の注目度）: 30.8580020414087
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study a new decision-making problem called the bandit max-min fair allocation (BMMFA) problem. The goal of this problem is to maximize the minimum utility among agents with additive valuations by repeatedly assigning indivisible goods to them. One key feature of this problem is that each agent's valuation for each item can only be observed through the semi-bandit feedback, while existing work supposes that the item values are provided at the beginning of each round. Another key feature is that the algorithm's reward function is not additive with respect to rounds, unlike most bandit-setting problems. Our first contribution is to propose an algorithm that has an asymptotic regret bound of $O(m\sqrt{T}\ln T/n + m\sqrt{T \ln(mnT)})$, where $n$ is the number of agents, $m$ is the number of items, and $T$ is the time horizon. This is based on a novel combination of bandit techniques and a resource allocation algorithm studied in the literature on competitive analysis. Our second contribution is to provide the regret lower bound of $\Omega(m\sqrt{T}/n)$. When $T$ is sufficiently larger than $n$, the gap between the upper and lower bounds is a logarithmic factor of $T$.
• Abstract（参考訳）: 本稿では,BMMFA問題と呼ばれる新たな意思決定問題について検討する。 この問題の目標は、不特定商品を繰り返し割り当てることにより、付加価値を持つエージェント間の最小限の効用を最大化することである。 この問題の1つの重要な特徴は、各アイテムに対する各エージェントのバリュエーションが半バンドフィードバックによってのみ観測可能であるのに対して、既存の作業は各ラウンドの開始時にアイテム値が提供されると仮定している。 もう一つの重要な特徴は、アルゴリズムの報酬関数が、ほとんどの帯域設定問題とは異なり、ラウンドに関して加法的でないことである。 最初のコントリビューションは、asymsymotic regret bound of $O(m\sqrt{T}\ln T/n + m\sqrt{T \ln(mnT)})$, where $n$ is the number of agent, $m$ is the number of items, $T$ is the time horizon。 これは、競争分析に関する文献で研究されているバンディット手法と資源配分アルゴリズムの新たな組み合わせに基づいている。 第二の貢献は、後悔の少ない$Omega(m\sqrt{T}/n)$を提供することである。 T$ が$n$ より十分大きいとき、上界と下界の間のギャップは$T$ の対数係数である。

関連論文リスト

• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  本稿では,非退化関数に対するバッチ帯域学習問題について検討する。 本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-09T12:50:16Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。 ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。 我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
  論文  参考訳（メタデータ） (2023-02-07T02:22:31Z)
• Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
  我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。 我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-03-29T15:27:13Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• No Regrets for Learning the Prior in Bandits [30.478188057004175]
  $tt AdaTS$は、バンディットタスクに順次適応するトンプソンサンプリングアルゴリズムである。 $tt AdaTS$は、バンドイト問題のいくつかのクラスで効率的に実装できる完全ベイズアルゴリズムである。
  論文  参考訳（メタデータ） (2021-07-13T15:51:32Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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