論文の概要: Double Explore-then-Commit: Asymptotic Optimality and Beyond

• arxiv url: http://arxiv.org/abs/2002.09174v2
• Date: Thu, 19 Nov 2020 07:40:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 00:45:18.484836
• Title: Double Explore-then-Commit: Asymptotic Optimality and Beyond
• Title（参考訳）: Double Explore-then-Commit: Asymptotic Optimality and Beyond
• Authors: Tianyuan Jin and Pan Xu and Xiaokui Xiao and Quanquan Gu
• Abstract要約: ガウス級報酬を用いたマルチアームバンディット問題について検討する。 本研究では,探索-then-commit (ETC) アルゴリズムの変種により,マルチアームバンディット問題に対する最適性が得られることを示す。
• 参考スコア（独自算出の注目度）: 101.77632893858063
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the multi-armed bandit problem with subgaussian rewards. The explore-then-commit (ETC) strategy, which consists of an exploration phase followed by an exploitation phase, is one of the most widely used algorithms in a variety of online decision applications. Nevertheless, it has been shown in Garivier et al. (2016) that ETC is suboptimal in the asymptotic sense as the horizon grows, and thus, is worse than fully sequential strategies such as Upper Confidence Bound (UCB). In this paper, we show that a variant of ETC algorithm can actually achieve the asymptotic optimality for multi-armed bandit problems as UCB-type algorithms do and extend it to the batched bandit setting. Specifically, we propose a double explore-then-commit (DETC) algorithm that has two exploration and exploitation phases and prove that DETC achieves the asymptotically optimal regret bound. To our knowledge, DETC is the first non-fully-sequential algorithm that achieves such asymptotic optimality. In addition, we extend DETC to batched bandit problems, where (i) the exploration process is split into a small number of batches and (ii) the round complexity is of central interest. We prove that a batched version of DETC can achieve the asymptotic optimality with only a constant round complexity. This is the first batched bandit algorithm that can attain the optimal asymptotic regret bound and optimal round complexity simultaneously.
• Abstract（参考訳）: サブガウシアン報酬を用いたマルチアームバンディット問題の研究を行った。 Explor-then-commit(ETC)戦略は、探索フェーズとエクスプロイトフェーズから構成され、様々なオンライン意思決定アプリケーションにおいて最も広く使われているアルゴリズムの1つである。 しかしながら、Garivier et al. (2016) では、地平線が大きくなるにつれて、ETCは漸近的な意味での準最適であり、上信頼境界(UCB)のような完全な逐次戦略よりも悪いことが示されている。 本稿では,UTB型アルゴリズムがバッチバンド設定に拡張するにつれて,ETCアルゴリズムの変種がマルチアームバンディット問題に対する漸近的最適性を実際に達成できることを示す。 具体的には,2つの探索と悪用フェーズを持つ二重探索-then-commit (DETC) アルゴリズムを提案する。 我々の知る限り、DETCはこのような漸近的最適性を達成する最初の非完全順序アルゴリズムである。 さらに、我々はDETCをバッチ化バンディット問題に拡張する。 (i)探索過程は、少数のバッチに分割される。 (ii) 丸い複雑さは中心的な関心事である。 我々は,DECのバッチバージョンが,一定のラウンド複雑性で漸近的最適性を達成できることを証明した。 これは、最適漸近的後悔境界と最適ラウンド複雑性を同時に達成できる最初のバッチバンディットアルゴリズムである。

関連論文リスト

• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
  論文  参考訳（メタデータ） (2023-10-24T09:47:32Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Non-Asymptotic Analysis of a UCB-based Top Two Algorithm [4.18804572788063]
  バンディット識別のためのトップ2サンプリングルールは、2つの候補アームの中から次のアームを選択する方法である。 提案するUCBベースのトップ2は,非漸近的保証と競合経験性能を同時に享受する。
  論文  参考訳（メタデータ） (2022-10-11T13:21:59Z)
• Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic [4.94128206910124]
  本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。 このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。 また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
  論文  参考訳（メタデータ） (2022-06-12T13:14:14Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Gamification of Pure Exploration for Linear Bandits [34.16123941778227]
  線形バンディットの文脈において、ベストアーム識別を含む活発な純粋探索環境について検討する。 標準的なマルチアームバンディットには最適アルゴリズムが存在するが、リニアバンディットにおけるベストアーム識別のためのアルゴリズムの存在は明白である。 線形帯域における固定信頼純粋探索のための第一の洞察的最適アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-07-02T08:20:35Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)

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

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