論文の概要: Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions
and Approximations
- arxiv url: http://arxiv.org/abs/2106.06712v1
- Date: Sat, 12 Jun 2021 08:14:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-15 15:50:18.583508
- Title: Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions
and Approximations
- Title（参考訳）: 組合せバンディットのための単純な組合せアルゴリズム:腐敗と近似
- Authors: Haike Xu, Jian Li
- Abstract要約: 我々は、$tildeOleft(C+d2K/Delta_minright)$の後悔を達成できる単純なアルゴリズムを提供する。
我々のアルゴリズムは非常に単純で、$sqrtd$で縛られた最もよく知られた後悔よりも悪いだけであり、以前の研究よりもはるかに低いオラクルの複雑さを持つ。
- 参考スコア（独自算出の注目度）: 6.2140753425381785
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the stochastic combinatorial semi-bandit problem with adversarial
corruptions. We provide a simple combinatorial algorithm that can achieve a
regret of $\tilde{O}\left(C+d^2K/\Delta_{min}\right)$ where $C$ is the total
amount of corruptions, $d$ is the maximal number of arms one can play in each
round, $K$ is the number of arms. If one selects only one arm in each round, we
achieves a regret of $\tilde{O}\left(C+\sum_{\Delta_i>0}(1/\Delta_i)\right)$.
Our algorithm is combinatorial and improves on the previous combinatorial
algorithm by [Gupta et al., COLT2019] (their bound is
$\tilde{O}\left(KC+\sum_{\Delta_i>0}(1/\Delta_i)\right)$), and almost matches
the best known bounds obtained by [Zimmert et al., ICML2019] and [Zimmert and
Seldin, AISTATS2019] (up to logarithmic factor). Note that the algorithms in
[Zimmert et al., ICML2019] and [Zimmert and Seldin, AISTATS2019] require one to
solve complex convex programs while our algorithm is combinatorial, very easy
to implement, requires weaker assumptions and has very low oracle complexity
and running time. We also study the setting where we only get access to an
approximation oracle for the stochastic combinatorial semi-bandit problem. Our
algorithm achieves an (approximation) regret bound of
$\tilde{O}\left(d\sqrt{KT}\right)$. Our algorithm is very simple, only worse
than the best known regret bound by $\sqrt{d}$, and has much lower oracle
complexity than previous work.
- Abstract（参考訳）: 敵対的腐敗を伴う確率的組合せ半バンド問題を考える。
単純な組合せアルゴリズムは、$\tilde{O}\left(C+d^2K/\Delta_{min}\right)$を後悔し、$C$は汚職の総量、$d$は各ラウンドでプレイできる武器の最大数、$K$は武器の数である。
各ラウンドで片方の腕だけを選ぶと、$\tilde{O}\left(C+\sum_{\Delta_i>0}(1/\Delta_i)\right)$を後悔する。
我々のアルゴリズムは, [Gupta et al., COLT2019] (その境界は$\tilde{O}\left(KC+\sum_{\Delta_i>0}(1/\Delta_i)\right)$) と, [Zimmert et al., ICML2019] と [Zimmert and Seldin, AISTATS2019] (対数係数まで) で得られた最もよく知られた境界にほぼ一致する。
Zimmert et al., ICML2019] と [Zimmert and Seldin, AISTATS2019] のアルゴリズムは複雑な凸プログラムを解く必要があり、我々のアルゴリズムは組合せ的であり、実装が非常に簡単であり、より弱い仮定を必要とし、オラクルの複雑さと実行時間が非常に低い。
また,確率的組合せ半帯域問題に対する近似オラクルにのみアクセス可能な設定についても検討した。
我々のアルゴリズムは、$\tilde{O}\left(d\sqrt{KT}\right)$の(近似)後悔境界を達成する。
我々のアルゴリズムは非常に単純で、$\sqrt{d}$で縛られる最もよく知られた後悔よりも悪く、以前の作業よりもはるかにオラクルの複雑さが低い。
関連論文リスト
- Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。
既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
論文 参考訳（メタデータ） (2023-10-17T19:43:37Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Statistically Efficient, Polynomial Time Algorithms for Combinatorial
Semi Bandits [3.9919781077062497]
アームの集合である$cal X の部分集合 0,1d$ 上の半帯域を考える。
この問題に対して、ESCB アルゴリズムは最小の既約値 $R(T) = cal OBig(d (ln m)2 (ln T) over Delta_min Big)$ を生成するが、計算複雑性 $cal O(|cal X|)$ を持つ。
論文 参考訳（メタデータ） (2020-02-17T21:32:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。