論文の概要: Covariance-Adaptive Least-Squares Algorithm for Stochastic Combinatorial
Semi-Bandits
- arxiv url: http://arxiv.org/abs/2402.15171v1
- Date: Fri, 23 Feb 2024 08:07:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-26 15:22:08.177917
- Title: Covariance-Adaptive Least-Squares Algorithm for Stochastic Combinatorial
Semi-Bandits
- Title(参考訳): 確率的組合せ半バンドに対する共分散適応最小二乗アルゴリズム
- Authors: Julien Zhou (Thoth, STATIFY), Pierre Gaillard (Thoth), Thibaud Rahier,
Houssam Zenati (SODA, PREMEDICAL), Julyan Arbel (STATIFY)
- Abstract要約: 我々は、プレイヤーが d 個の基本項目を含む集合の P 部分集合から選択できる半帯域の問題に対処する。
我々は,共分散構造のオンライン推定に頼って,OLS-UCBの分散適応バージョンを設計する。
- 参考スコア(独自算出の注目度): 2.97816271115804
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of stochastic combinatorial semi-bandits, where a
player can select from P subsets of a set containing d base items. Most
existing algorithms (e.g. CUCB, ESCB, OLS-UCB) require prior knowledge on the
reward distribution, like an upper bound on a sub-Gaussian proxy-variance,
which is hard to estimate tightly. In this work, we design a variance-adaptive
version of OLS-UCB, relying on an online estimation of the covariance
structure. Estimating the coefficients of a covariance matrix is much more
manageable in practical settings and results in improved regret upper bounds
compared to proxy variance-based algorithms. When covariance coefficients are
all non-negative, we show that our approach efficiently leverages the
semi-bandit feedback and provably outperforms bandit feedback approaches, not
only in exponential regimes where P $\gg$ d but also when P $\le$ d, which is
not straightforward from most existing analyses.
- Abstract(参考訳): 確率的組合せ半帯域の問題に対処し、プレイヤーは d 個の基本項目を含む集合の P 部分集合から選択できる。
ほとんどの既存のアルゴリズム(CUCB, ESCB, OLS-UCB)は報酬分布に関する事前知識を必要とする。
本研究では,OLS-UCBの分散適応バージョンを設計し,共分散構造をオンラインで推定する。
共分散行列の係数の推定は、実際的な設定ではずっと管理可能であり、プロキシ分散ベースのアルゴリズムと比較して、後悔の上限が改善される。
共分散係数がすべて非負である場合、我々の手法は半帯域フィードバックを効率よく利用し、P$\gg$ d の指数的状態だけでなく、P$\le$ d の指数的状態においてもバンドフィードバックアプローチを確実に上回ることを示す。
関連論文リスト
- Batch and match: black-box variational inference with a score-based
divergence [28.220604905700192]
バッチ・アンド・マッチ (BaM) は、スコアベースの発散に基づくブラックボックス変分推論のアプローチである。
BaM は ELBO に基づく BBVI の先行実装よりも勾配評価が小さい。
論文 参考訳(メタデータ) (2024-02-22T18:20:22Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Efficiently Escaping Saddle Points for Non-Convex Policy Optimization [40.0986936439803]
政策勾配(PG)は、拡張性と優れた性能のために強化学習に広く用いられている。
本稿では,ヘッセンベクトル積 (HVP) の形で二階情報を用いた分散還元二階法を提案し,サンプルの複雑さを$tildeO(epsilon-3)$とする近似二階定常点 (SOSP) に収束する。
論文 参考訳(メタデータ) (2023-11-15T12:36:45Z) - 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) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳(メタデータ) (2022-10-08T08:26:22Z) - Adversarially Robust Multi-Armed Bandit Algorithm with
Variance-Dependent Regret Bounds [34.37963000493442]
本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-06-14T12:58:46Z) - Optimal Clustering with Bandit Feedback [84.04424523097168]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳(メタデータ) (2021-10-20T02:25:25Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-21T00:56:33Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。