論文の概要: Balanced Sampling in Stochastic Multi-objective Bandits
- arxiv url: http://arxiv.org/abs/2610.35551v1
- Date: Mon, 26 Oct 2026 14:55:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-27 22:27:14.042751
- Title: Balanced Sampling in Stochastic Multi-objective Bandits
- Title（参考訳）: 確率的多目的帯域における平衡サンプリング
- Abstract要約: 我々は、真のパレート集合上の一様分布からサンプリング軌道によって誘導される経験的測度へのKL偏差による不公平度を測定する。
我々は、アンダーサンプアームの探索を奨励し、永続的なアンダーアロケーションのリスクを低減する変種を作成します。
- 参考スコア（独自算出の注目度）: 5.260137087369842
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In stochastic multi-objective bandits, Pareto optimal arms may represent different trade-offs among objectives. Balanced sampling across them is important in practical settings such as online advertising. Yet, there seems to be little consensus on how to measure fairness, to our best knowledge. Achieving fairness is also tough as the set of Pareto optimal arms is unknown, and early sampling decisions may create imbalances that are difficult to erase afterwards. We measure unfairness by the KL divergence from the uniform distribution over the true Pareto set to the empirical measure induced by the sampling trajectory. Nicely, this measure admits an exact decomposition that separates the cost of sampling suboptimal arms from the imbalance among Pareto optimal arms. With a recursive form for unfairness, we develop \emph{adaptive top-two sampling}, which combines sampling counts and empirical evidence of Pareto membership to define a gain for each arm and guide sampling without committing to an estimated Pareto set. When the Pareto set is stable under small perturbations, we establish an $O(\log T/T)$ and $O(T^{-1})$ bound on expected unfairness and variance, respectively. Information-theoretic lower bounds show that the $\log T/T$ rate can be unavoidable for uniformly fair policies on stable instances, matching our upper bound. More surprisingly, stability is indeed crucial, as the expected unfairness can be $ω(\log T/T)$ without it. Finally, we create a variant that encourages exploration of undersampled arms to reduce the risk of persistent underallocation. At sufficiently large horizons, it preserves the rate on the expected unfairness while admitting a sharper bound of $O(\log^2 T/T^2)$ on variance. Numerical studies support these findings and suggest practical insights.
- Abstract（参考訳）: 確率的多目的包帯では、パレートの最適腕は目的によって異なるトレードオフを表すことがある。
バランスの取れたサンプリングは、オンライン広告のような実践的な設定において重要である。
しかし、私たちの最高の知識に対して公平さを測る方法については、ほとんど合意が得られていないようです。
パレートの最適な腕のセットが未知であるため、公平さの達成も困難であり、初期のサンプリング決定はその後消し去るのが難しい不均衡を生じさせる可能性がある。
我々は、真のパレート集合上の一様分布からサンプリング軌道によって誘導される経験的測度へのKL偏差による不公平度を測定する。
興味深いことに、この尺度はパレートの最適腕の不均衡から最適腕をサンプリングするコストを分離する正確な分解を認めている。
不公平性のための再帰的な形式を用いて、推定されたパレート集合にコミットすることなく、各腕の利得を定義するためにサンプリング数とパレートメンバーシップの実証的証拠を組み合わせた「emph{adaptive top-two sample」を開発する。
パレート集合が小さな摂動の下で安定であるとき、それぞれ期待される不公平さと分散に基づく$O(\log T/T)$と$O(T^{-1})$を確立する。
情報理論の下限は、$\log T/T$ レートが安定なインスタンスに対する一様公正なポリシーに対して避けられないことを示す。
さらに驚くべきことに、期待される不公平さは、それなしでは$ω(\log T/T)$であるので、安定性は本当に重要である。
最後に、持続的な下転のリスクを低減するために、アンダーサンプアームの探索を奨励する変異体を作成します。
十分に大きな地平線では、予想される不公平さの速度を保ちながら、分散に関してよりシャープな$O(\log^2 T/T^2)を許容する。
数値的な研究はこれらの発見を支持し、実践的な洞察を示唆している。
関連論文リスト
- Adaptive Robust Confidence Sets in High Dimensions [60.353542776481596]
本研究では,不確実性を同時に定量化することにより,情報理論的に最適な適応信頼セットを構築することができることを示す。
統計的には最適であるが、この構成は計算的に不可能である。
論文 参考訳（メタデータ） (2026-10-11T16:00:46Z) - Robust Importance Sampling for Rare Events via Constrained Gaussian Mixtures [0.0]
I = mathbbP(g(mathbfX) > )$ with $mathbfX sim mathcalN(boldsymbol, boldsymbol)$ and general $g : mathbbRd to mathbbR$。
本稿では,この課題を重要サンプリングを通じて解決し,ベースラインよりも効率と堅牢性を大幅に向上させるフレームワークを提案する。
論文 参考訳（メタデータ） (2026-10-05T22:49:19Z) - Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise [66.13091490213743]
グラディエントクリッピングはトレーニングを安定させるために広く用いられているが、平均的なSGDの統計的精度を改善する必要はない。
有限条件の$p$-th モーメント,$pge2$ の条件下で, クリッピングおよび非クリッピングのPolyak-Ruppert平均 SGD の比較を導出した。
我々の主な結果は、$p>2$の場合、ガウス項が未開偏差境界を独占する明確な精度と信頼条件を与える。
論文 参考訳（メタデータ） (2026-09-26T21:47:14Z) - Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。
我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
論文 参考訳（メタデータ） (2026-08-06T19:49:48Z) - When Are Trade-Off Functions Testable from Finite Samples? [4.706977254727891]
2つの未知確率分布のトレードオフ関数に対する有限サンプル推論について検討する。
テストの反転により、トレードオフ曲線全体に対する同時信頼バンドも得られる。
論文 参考訳（メタデータ） (2026-05-11T16:07:48Z) - Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret [71.69884486156359]
我々は, 累積的不完全化予算を用いて, エンフルティソースの不完全性選好からエピソードRLを考察した。
我々は,最良な登録行動を示す,後悔$tildeO(sqrtK/M+)$の統一アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-03-20T19:34:53Z) - Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions [4.200594864147057]
複数の確率変数に対して$p$の独立性をテストする問題に対処する。
補助的だが信頼できない、予測可能な情報を組み込んだテスタを設計します。
我々のフレームワークは、予測の品質に関わらず、テスターが堅牢で、最悪のケースの妥当性を維持することを保証します。
論文 参考訳（メタデータ） (2026-03-04T21:55:08Z) - Optimism Stabilizes Thompson Sampling for Adaptive Inference [9.558593674952654]
トンプソンサンプリング(TS)は多武装の包帯に広く用いられているが、適応データ収集における推論特性は微妙である。
我々は、この現象を$K$武器のガウス・バンディットで研究し、エンホプティミズムをエンホスタビリティの回復の鍵となるメカニズムとして認識する。
分散膨張型TS citephalder2025stableは、複数のアームが最適である難易度を含む、任意のK ge 2$に対して安定であることを示す。
論文 参考訳（メタデータ） (2026-02-05T18:52:54Z) - From Fragile to Certified: Wasserstein Audits of Group Fairness Under Distribution Shift [21.387312729118364]
グループフェアネスの指標は、再サンプル間で大きく変化し、特に分散シフト下では不安定である。
本稿では, 実験法則を中心にした有理テスト分布の球面上で最悪の群フェアネスを証明した, 分布的に堅牢なワッサーシュタインフレームワークを提案する。
論文 参考訳（メタデータ） (2025-09-30T13:35:50Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。