論文の概要: The Pareto Frontier of model selection for general Contextual Bandits

• arxiv url: http://arxiv.org/abs/2110.13282v1
• Date: Mon, 25 Oct 2021 21:44:35 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-27 15:23:16.470065
• Title: The Pareto Frontier of model selection for general Contextual Bandits
• Title（参考訳）: 一般文脈帯域におけるモデル選択のパレートフロンティア
• Authors: Teodor V. Marinov and Julian Zimmert
• Abstract要約: 我々は、ネストしたポリシークラスの全てのポリシーを保証できる最適な単一アルゴリズムを同時に得ることができるかどうかを問う。また、もしそうでなければ、複雑性項と時間の間のトレードオフ$alphain[frac12,1)$に対して可能である: $ln(|Pi_m|)1-alphaTalpha$。 上界と下界に一致する最大対数因子のフロンティアを示すので、一般の政策では$T$とは独立な複雑性項 $ln(|Pi_m|)$ の増加は避けられないことを証明できる。
• 参考スコア（独自算出の注目度）: 15.454070036560388
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent progress in model selection raises the question of the fundamental limits of these techniques. Under specific scrutiny has been model selection for general contextual bandits with nested policy classes, resulting in a COLT2020 open problem. It asks whether it is possible to obtain simultaneously the optimal single algorithm guarantees over all policies in a nested sequence of policy classes, or if otherwise this is possible for a trade-off $\alpha\in[\frac{1}{2},1)$ between complexity term and time: $\ln(|\Pi_m|)^{1-\alpha}T^\alpha$. We give a disappointing answer to this question. Even in the purely stochastic regime, the desired results are unobtainable. We present a Pareto frontier of up to logarithmic factors matching upper and lower bounds, thereby proving that an increase in the complexity term $\ln(|\Pi_m|)$ independent of $T$ is unavoidable for general policy classes. As a side result, we also resolve a COLT2016 open problem concerning second-order bounds in full-information games.
• Abstract（参考訳）: モデル選択の最近の進歩は、これらの技術の基本的限界を提起する。 特定の監視の下では、ネストしたポリシークラスを持つ一般的なコンテキストバンディットのモデル選択が行われ、colt2020のオープン問題が発生した。 これは、ネストされたポリシークラス内のすべてのポリシーに対して、最適な1つのアルゴリズムを同時に得ることができるかどうかを問うものであるが、そうでなければ、複雑性項と時間の間に$\ln(|\pi_m|)^{1-\alpha}t^\alpha$というトレードオフに対して可能である。 私たちはこの質問に残念な答えをする。 純粋に確率的な体制であっても、望ましい結果が得られない。 上界と下界に一致する対数的因子のパレートフロンティアを示すので、一般的な政策クラスでは$T$とは独立な複雑性項 $\ln(|\Pi_m|)$ の増加は避けられない。 結果として,全情報ゲームにおける2次境界に関するcolt2016オープン問題を解決した。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Generalized Linear Bandits with Limited Adaptivity [12.112051468737596]
  限定適応性の制約内における一般化線形文脈帯域問題について検討する。 我々は2つのアルゴリズム, $textttB-GLinCB$ と $textttRS-GLinCB$ を提示した。
  論文  参考訳（メタデータ） (2024-04-10T08:47:57Z)
• Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption [12.471848976031904]
  基本的な目標は、腕の数($N$)が大きくなるにつれて、最適性のギャップを小さくするポリシーを効率的に計算することである。 既存の最適性に関する結果は、すべて一様大域的誘引特性(UGAP)に依存している。 我々は,任意の単一武器のポリシーを元の$N$武器の問題に対するポリシーに変換する,汎用的なシミュレーションベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-05-31T21:26:43Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond [18.176606453818557]
  有限サム最小化問題を解くための勾配勾配勾配勾配(SGD)について述べる。 Random Reshuffling の場合、既存の境界よりも$kappa$ がより狭い境界が見つかる。
  論文  参考訳（メタデータ） (2023-03-13T14:35:55Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。 この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
  論文  参考訳（メタデータ） (2023-03-06T17:54:33Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach [37.80609997145897]
  強化学習は、環境と対話しながらシーケンシャルな決定を行う必要があるアプリケーションで広く使われている。 決定要件がいくつかの安全制約を満たすことを含むと、問題はより難しくなります。 CMDP問題をモデルのない方法で解き、$epsilon$-optimal cumulative rewardを$epsilon$-factible Policyで達成することができる。 ここでの重要な疑問は、制約違反ゼロで$epsilon$-optimal cumulative rewardを達成できるかどうかである。
  論文  参考訳（メタデータ） (2021-09-13T21:27:03Z)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。 学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。 コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
  論文  参考訳（メタデータ） (2021-06-18T15:01:01Z)

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

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