論文の概要: Regret Bound Balancing and Elimination for Model Selection in Bandits and RL

• arxiv url: http://arxiv.org/abs/2012.13045v1
• Date: Thu, 24 Dec 2020 00:53:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-25 08:28:08.741616
• Title: Regret Bound Balancing and Elimination for Model Selection in Bandits and RL
• Title（参考訳）: バンディットとrlにおけるモデル選択のための後悔境界バランスと除去
• Authors: Aldo Pacchiano, Christoph Dann, Claudio Gentile, Peter Bartlett
• Abstract要約: バンディットおよび強化学習問題におけるアルゴリズムの簡易モデル選択手法を提案する。 我々は、このアプローチの総後悔は、最も有効な候補者の後悔の回数が乗算的要因であることを証明します。 線形バンディットのモデル選択における最近の取り組みとは違って,我々のアプローチは,敵の環境によってコンテキスト情報が生成されるケースをカバーできるほど多用途である。
• 参考スコア（独自算出の注目度）: 34.15978290083909
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a simple model selection approach for algorithms in stochastic bandit and reinforcement learning problems. As opposed to prior work that (implicitly) assumes knowledge of the optimal regret, we only require that each base algorithm comes with a candidate regret bound that may or may not hold during all rounds. In each round, our approach plays a base algorithm to keep the candidate regret bounds of all remaining base algorithms balanced, and eliminates algorithms that violate their candidate bound. We prove that the total regret of this approach is bounded by the best valid candidate regret bound times a multiplicative factor. This factor is reasonably small in several applications, including linear bandits and MDPs with nested function classes, linear bandits with unknown misspecification, and LinUCB applied to linear bandits with different confidence parameters. We further show that, under a suitable gap-assumption, this factor only scales with the number of base algorithms and not their complexity when the number of rounds is large enough. Finally, unlike recent efforts in model selection for linear stochastic bandits, our approach is versatile enough to also cover cases where the context information is generated by an adversarial environment, rather than a stochastic one.
• Abstract（参考訳）: 本稿では,確率的バンディットと強化学習問題のアルゴリズムに対する簡単なモデル選択手法を提案する。 単純に)最適後悔の知識を仮定する以前の研究とは対照的に、各基本アルゴリズムは全てのラウンドで保持されるかもしれないし、持たないかもしれない、候補の後悔境界を持つ必要がある。 各ラウンドにおいて、我々の手法は、残されている全ての基本アルゴリズムの残差の残差を保ち、その候補境界に違反するアルゴリズムを排除するために、基本アルゴリズムを実行する。 このアプローチの完全な後悔は、最も有効な候補の後悔の時間と乗法的要因によって境界づけられていることを証明する。 この因子は、ネスト関数クラスを持つ線形包帯やMDP、未知の不特定な線形包帯、異なる信頼パラメータを持つ線形包帯に適用されるLinUCBなど、いくつかの応用において合理的に小さい。 さらに、適切なギャップ推定の下では、この因子は基本アルゴリズムの数でしかスケールせず、ラウンド数が十分に大きい場合の複雑さも示さない。 最後に、線形確率的包帯のモデル選択における最近の取り組みとは異なり、我々のアプローチは、確率的ではなく対向的な環境によって文脈情報が生成されるケースをカバーできる。

関連論文リスト

• Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
  モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。 我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
  論文  参考訳（メタデータ） (2023-12-24T07:46:37Z)
• Universal and data-adaptive algorithms for model selection in linear contextual bandits [52.47796554359261]
  モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。 データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。 我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
  論文  参考訳（メタデータ） (2021-11-08T18:05:35Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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