論文の概要: Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret
- arxiv url: http://arxiv.org/abs/2610.07737v1
- Date: Tue, 06 Oct 2026 04:32:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 02:58:29.800708
- Title: Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret
- Title（参考訳）: マルチアームバンドのためのナッシュ社会福祉 : 軌道知能と高い確率レグレット
- Abstract要約: 我々は、Nash Social Welfare(NSW)の目的の下で、公正なマルチ武器の盗賊について研究する。
既存の作業では、ナッシュの後悔を$mathrmNR_T = star - (prod_t=1T mathbbE_I_t)1/T$と定義している。
我々は,Emphtrajectory-wise Nash regret $widetildemathrmNR_T = star - mathbbE[(prod_t=1T _を提案する。
- 参考スコア（独自算出の注目度）: 10.42358047828068
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study fair multi-armed bandits under the Nash Social Welfare (NSW) objective, which measures performance via the geometric mean of accumulated rewards. Existing work defines Nash regret as $\mathrm{NR}_T = μ^\star - (\prod_{t=1}^T \mathbb{E}μ_{I_t})^{1/T}$, where $μ_{I_t}$ is the mean reward of the recommended arm $I_t$ and $T$ is the horizon. Since it applies the geometric mean to per-round marginal expectations, it ignores the joint distribution of rewards across rounds, leaving the NSW fairness motivation unaddressed at the trajectory level. We propose \emph{trajectory-wise Nash regret} $\widetilde{\mathrm{NR}}_T = μ^\star - \mathbb{E}[(\prod_{t=1}^T μ_{I_t})^{1/T}]$, which computes the geometric mean over complete sample paths before taking expectations, capturing NSW fairness more faithfully. By Jensen's inequality, $\widetilde{\mathrm{NR}}_T \geq \mathrm{NR}_T$, making it a strictly stronger metric. We also introduce \emph{high probability Nash regret} $\widehat{\mathrm{NR}}_T = μ^\star - (\prod_t μ_{I_t})^{1/T}$, giving the first high probability regret bounds in fair bandits. Our two-phase algorithm, Round Robin Nash Confidence Bound (\texttt{RR-NCB}), combines round robin exploration with a Nash confidence bound index policy. We show $\widetilde{\mathrm{NR}}_T \leq \widetilde{\mathcal{O}}(\sqrt{k\log T/T})$ and, with probability $1-δ$, $\widehat{\mathrm{NR}}_T \leq \widetilde{\mathcal{O}}(\sqrt{k\log(kT/δ)/T})$, matching the optimal $\widetilde{\mathcal{O}}(\sqrt{k/T})$ rate despite the stronger metrics. Optimality follows from a lower bound via AM-GM and standard $k$-armed bandit minimax arguments. Simulations validate our theory.
- Abstract（参考訳）: Nash Social Welfare (NSW) の目的の下で, 蓄積した報酬の幾何学的平均を用いて, パフォーマンスを計測する, 公平なマルチアームバンディットについて検討した。
既存の作業では、ナッシュの後悔を$\mathrm{NR}_T = μ^\star - (\prod_{t=1}^T \mathbb{E}μ_{I_t})^{1/T}$と定義している。
幾何学的平均を辺縁予想の周囲に当てはめるため、ラウンド全体での報酬の分配を無視し、NSWフェアネスモチベーションを軌跡レベルに含めないままにする。
予想を下す前に、完全なサンプルパス上の幾何学的平均を計算し、NSWフェアネスをより忠実に取得する。
イェンセンの不等式により、$\widetilde{\mathrm{NR}}_T \geq \mathrm{NR}_T$ となる。
また、emph{high probability Nash regret} $\widehat{\mathrm{NR}}_T = μ^\star - (\prod_t μ_{I_t})^{1/T}$を導入し、公正な包帯において最初の高い確率後悔境界を与える。
我々の2相アルゴリズムであるRound Robin Nash Confidence Bound (\texttt{RR-NCB})は、ラウンドロビン探索とNashの信頼性バウンドインデックスポリシを組み合わせる。
例えば、$\widetilde{\mathrm{NR}}_T \leq \widetilde{\mathcal{O}}(\sqrt{k\log T/T})$, and with probability $1-δ$, $\widehat{\mathrm{NR}}_T \leq \widete{\mathcal{O}}(\sqrt{k\log(kT/δ)/T})$, and with the probability $1-δ$, $\widehat{\mathrm{NR}}_T \leq \widede{\mathcal{O}}(\sqrt{k/T})$。
最適性は、AM-GMと標準の$k$-armed bandit minimax引き数による下限から従う。
シミュレーションは我々の理論を検証する。
関連論文リスト
- Price of Fairness in Bandits: A Tight Minimax Characterization [9.360852329235477]
盗賊問題では、標準的な後悔を最小化するアルゴリズムが探索を償却コストとして扱い、初期の参加者は不公平な前衛の損失に晒される。
最近の研究は、一般化された$p$-meanを通じて、ラウンドごとの期待される報酬のシーケンスを評価することで、この問題に対処している。
アルゴリズムに依存しない下界$(sqrtkmax(1,q)/T)$; for $q>1$, this shows that $kq/2$ is a information-theoretically unavoidable。
論文 参考訳（メタデータ） (2026-07-15T02:58:57Z) - A 1/R Law for Kurtosis Contrast in Balanced Mixtures [15.412858526786978]
クルトーシスに基づく独立成分分析は、幅広いバランスの取れた混合物を弱める。
有効幅が$R_mathrmeff$の標準化された射影に対して、人口超過は$|(y)|=O(_max/R_mathrmeff)$に従う。
また、emphpurification -- selecting $m!ll!R$ sign-consistent sources -- restores $R$-independent contrast $ (1/m)$, with a simple data.
論文 参考訳（メタデータ） (2026-02-25T19:01:01Z) - Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach [26.085126064745378]
そこでは,N$エージェントが協力してグローバルな平均損失を最小限に抑えつつ,ローカルな損失のみを観察する。
この問題のミニマックス後悔は$tilde(sqrt(-1/2+K/N)T)$であり、$T$は地平線、$K$は行動の数、$は通信行列のスペクトルギャップである。
論文 参考訳（メタデータ） (2026-02-06T05:53:38Z) - Stochastic Linear Bandits with Parameter Noise [36.09200986359924]
ここでは、水平方向の$T$に対する$widetildeO (sqrtd T log (K/) 2_max)$、次元$d$の$K$の一般的なアクションセット、そして、$_max$が任意のアクションに対する報酬の最大分散であることを示す。
驚くべきことに、この最適(対数的要因による)後悔境界は、非常に単純な探索探索アルゴリズムを用いて達成可能であることを示す。
論文 参考訳（メタデータ） (2026-01-30T16:47:42Z) - Enjoying Non-linearity in Multinomial Logistic Bandits [56.28491566735463]
我々は,学習者が期待される報酬を最大化するために行動を選択することで,学習者が環境と相互作用する,多項ロジスティック・バンディット問題を考える。
本稿では,ロジスティックモデルの非線形性の影響を多項集合に拡張し,効率的なアルゴリズムを提案する。
我々のメソッドは、次数 $ smashwidetildemathcalO(R d sqrtKT/kappa_*)$ の問題依存的後悔境界を生じる。
論文 参考訳（メタデータ） (2025-07-07T08:18:25Z) - Nash Regret Guarantees for Linear Bandits [12.494184403263338]
我々は,Nashが$Oleft(sqrtfracdnuT log(T |X|)right)$を後悔するアルゴリズムを開発した。
さらに、アームの集合 X$ が必ずしも有限ではない線形バンドイットのインスタンスに対処すると、ナッシュ後悔の上限 $Oleft( fracdfrac54nufrac12sqrtT log(T)right)$ が得られる。
論文 参考訳（メタデータ） (2023-10-03T12:58:10Z) - Context-lumpable stochastic bandits [49.024050919419366]
我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。
我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。
後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-06-22T17:20:30Z) - 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) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。
Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
論文 参考訳（メタデータ） (2020-01-25T14:44:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。