論文の概要: Covariance-adapting algorithm for semi-bandits with application to sparse rewards

• arxiv url: http://arxiv.org/abs/2604.13738v1
• Date: Wed, 15 Apr 2026 11:27:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-16 20:38:32.506133
• Title: Covariance-adapting algorithm for semi-bandits with application to sparse rewards
• Title（参考訳）: 半帯域の共分散適応アルゴリズムとスパース報酬への応用
• Authors: Pierre Perrault, Vianney Perchet, Michal Valko,
• Abstract要約: 我々は、有界分布とガウス分布を含む部分指数分布の新しい族を考える。 我々は、この家族に対する期待された後悔に対して、新たな低い限界を証明している。 次に、共分散推定を用いたアルゴリズムを構築し、後悔の厳密な分析を行う。
• 参考スコア（独自算出の注目度）: 43.942639292139425
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate stochastic combinatorial semi-bandits, where the entire joint distribution of outcomes impacts the complexity of the problem instance (unlike in the standard bandits). Typical distributions considered depend on specific parameter values, whose prior knowledge is required in theory but quite difficult to estimate in practice; an example is the commonly assumed sub-Gaussian family. We alleviate this issue by instead considering a new general family of sub-exponential distributions, which contains bounded and Gaussian ones. We prove a new lower bound on the expected regret on this family, that is parameterized by the unknown covariance matrix of outcomes, a tighter quantity than the sub-Gaussian matrix. We then construct an algorithm that uses covariance estimates, and provide a tight asymptotic analysis of the regret. Finally, we apply and extend our results to the family of sparse outcomes, which has applications in many recommender systems.
• Abstract（参考訳）: 結果の連立分布が問題インスタンスの複雑さに影響を及ぼす確率的組合せ半帯域について検討する。 考慮される典型的な分布は特定のパラメータ値に依存しており、その事前の知識は理論上必要だが、実際に見積もるのは極めて困難である。 我々は代わりに、有界分布とガウス分布を含む新しい部分指数分布の一般族を考えることでこの問題を緩和する。 結果の未知の共分散行列によってパラメータ化され、ガウス行列よりも厳密な量である。 次に,共分散推定を用いたアルゴリズムを構築し,後悔の漸近解析を行う。 最後に、多くのレコメンデーションシステムに応用可能なスパース結果の族に適用し、拡張する。

関連論文リスト

• Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problem [16.04977600068383]
  我々は、厳密な情報理論の一般化誤差境界(すなわち、定数さえ一致する)を提供する。 既存の境界はこの設定で順序的に緩い。 その後、分解可能な損失関数に対して洗練された境界が提案され、ベクトル設定に対して厳密な境界が導かれる。
  論文  参考訳（メタデータ） (2023-05-01T15:22:58Z)
• A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms [14.33758865948252]
  我々は2つの有名なバンディットアルゴリズム、Minimum Empirical Divergence (MED)とThompson Sampling (TS)を再検討する。 MEDがこれらのモデルすべてに最適であることを示すとともに、最適性がすでに知られているTSアルゴリズムの簡単な後悔解析も提供する。
  論文  参考訳（メタデータ） (2023-03-10T16:43:48Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  我々は,高次元ロバストな統計問題を解くためにGAN(Generative Adversarial Networks)を設計するためのフレームワークを提供する。 我々の研究は、これらをロバスト平均推定、第二モーメント推定、ロバスト線形回帰に拡張する。 技術面では、提案したGAN損失は、スムーズで一般化されたコルモゴロフ-スミルノフ距離と見なすことができる。
  論文  参考訳（メタデータ） (2022-02-02T20:11:33Z)
• From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits [0.0]
  本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。 この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
  論文  参考訳（メタデータ） (2021-11-18T14:34:21Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  ガウス過程後部をシミュレーションするための従来のアプローチでは、有限個の入力位置のプロセス値の限界分布からサンプルを抽出する。 この分布中心の特徴づけは、所望のランダムベクトルのサイズで3次スケールする生成戦略をもたらす。 条件付けのこのパスワイズ解釈が、ガウス過程の後部を効率的にサンプリングするのに役立てる近似の一般族をいかに生み出すかを示す。
  論文  参考訳（メタデータ） (2020-11-08T17:09:37Z)
• Relative Deviation Margin Bounds [55.22251993239944]
  我々はRademacher複雑性の観点から、分布依存と一般家庭に有効な2種類の学習境界を与える。 有限モーメントの仮定の下で、非有界な損失関数に対する分布依存的一般化境界を導出する。
  論文  参考訳（メタデータ） (2020-06-26T12:37:17Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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