論文の概要: Online Generalized-mean Welfare Maximization: Achieving Near-Optimal Regret from Samples
- arxiv url: http://arxiv.org/abs/2602.10469v1
- Date: Wed, 11 Feb 2026 03:16:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-12 21:44:01.420212
- Title: Online Generalized-mean Welfare Maximization: Achieving Near-Optimal Regret from Samples
- Title（参考訳）: オンライン一般平均福祉最大化:サンプルからほぼ最適レグレットを得る
- Authors: Zongjun Yang, Rachitesh Kumar, Christian Kroer,
- Abstract要約: 我々は、不均一な好みを持つ$n$エージェントのうち、連続的に到着する$T$のオンラインフェアアロケーションについて検討した。
純粋欲求アルゴリズム(ミオプティックに福祉最大化積分割当を選択する)が平均的後悔の$widetildeO(1/T)を達成していることを示す。
- 参考スコア（独自算出の注目度）: 29.8171362564092
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online fair allocation of $T$ sequentially arriving items among $n$ agents with heterogeneous preferences, with the objective of maximizing generalized-mean welfare, defined as the $p$-mean of agents' time-averaged utilities, with $p\in (-\infty, 1)$. We first consider the i.i.d. arrival model and show that the pure greedy algorithm -- which myopically chooses the welfare-maximizing integral allocation -- achieves $\widetilde{O}(1/T)$ average regret. Importantly, in contrast to prior work, our algorithm does not require distributional knowledge and achieves the optimal regret rate using only the online samples. We then go beyond i.i.d. arrivals and investigate a nonstationary model with time-varying independent distributions. In the absence of additional data about the distributions, it is known that every online algorithm must suffer $Ω(1)$ average regret. We show that only a single historical sample from each distribution is sufficient to recover the optimal $\widetilde{O}(1/T)$ average regret rate, even in the face of arbitrary non-stationarity. Our algorithms are based on the re-solving paradigm: they assume that the remaining items will be the ones seen historically in those periods and solve the resulting welfare-maximization problem to determine the decision in every period. Finally, we also account for distribution shifts that may distort the fidelity of historical samples and show that the performance of our re-solving algorithms is robust to such shifts.
- Abstract（参考訳）: エージェントの時間平均ユーティリティの$p$-meanとして定義された一般化平均福祉を最大化することを目的として, 異種嗜好を持つ$n$エージェントのうち, 連続的に到着する$T$のオンラインフェアアロケーションを$p\in (-\infty, 1)$で検討した。
まず、i.d.到着モデルについて考察し、純粋欲求アルゴリズム(ミオプティックに福祉最大化積分割り当てを選択する)が平均後悔として$\widetilde{O}(1/T)を達成していることを示す。
重要なことは、従来の研究とは対照的に、我々のアルゴリズムは分布的な知識を必要とせず、オンラインサンプルのみを用いて最適な後悔率を達成することである。
その後、i.d.到着を超越し、時間変化の独立分布を持つ非定常モデルを調べる。
分布に関する追加データがない場合、全てのオンラインアルゴリズムは平均後悔の$Ω(1)$$$でなければならないことが知られている。
任意の非定常性に直面した場合でも,各分布からの1つの履歴サンプルのみが最適$\widetilde{O}(1/T)$平均後悔率を回復するのに十分であることを示す。
我々のアルゴリズムは、解決パラダイムに基づいており、残りの項目は、これらの期間で歴史的に見られたものであると仮定し、その結果の福祉最大化問題を解決し、各期間における決定を決定する。
最後に、過去のサンプルの忠実度を歪ませる分布シフトについても説明し、再解法アルゴリズムの性能がそのようなシフトに対して堅牢であることを示す。
関連論文リスト
- Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - 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) - Semi-Bandit Learning for Monotone Stochastic Optimization [16.921694787482213]
一般的なオンライン学習アルゴリズムは「モノトーン」問題のクラスのために開発されている。
当社のフレームワークは,預言不平等やPandoraのボックス,単一リソースの収益管理,ポスト価格など,いくつかの基本的な問題に適用しています。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - 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) - Contextual Decision-Making with Knapsacks Beyond the Worst Case [5.65888994172721]
資源制約を伴う動的意思決定シナリオの枠組みについて検討する。
このフレームワークでは、エージェントがランダムな要求を観察すると、各ラウンドでアクションを選択する。
我々のアルゴリズムは最悪の場合であっても、ほぼ最適の$widetildeO(sqrtT)$ regretを維持していることを証明している。
論文 参考訳（メタデータ） (2022-11-25T08:21:50Z) - Distributed Sparse Regression via Penalization [5.990069843501885]
エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
論文 参考訳（メタデータ） (2021-11-12T01:51:50Z) - On Reward-Free RL with Kernel and Neural Function Approximations:
Single-Agent MDP and Markov Game [140.19656665344917]
エージェントが事前に特定された報酬関数を使わずに環境を徹底的に探索することを目的とした報酬のないRL問題について検討する。
関数近似の文脈でこの問題に取り組み、強力な関数近似器を活用する。
我々は、カーネルとニューラルファンクション近似器を用いた、証明可能な効率の良い報酬なしRLアルゴリズムを確立した。
論文 参考訳（メタデータ） (2021-10-19T07:26:33Z) - Robust Learning of Optimal Auctions [84.13356290199603]
本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。
我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-07-13T17:37:21Z) - Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
論文 参考訳（メタデータ） (2020-12-13T04:47:37Z) - Approximation Schemes for ReLU Regression [80.33702497406632]
我々はReLU回帰の根本的な問題を考察する。
目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
論文 参考訳（メタデータ） (2020-05-26T16:26:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。