論文の概要: Instance-optimal PAC Algorithms for Contextual Bandits

• arxiv url: http://arxiv.org/abs/2207.02357v1
• Date: Tue, 5 Jul 2022 23:19:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-07 12:49:15.574969
• Title: Instance-optimal PAC Algorithms for Contextual Bandits
• Title（参考訳）: コンテキストバンディットのインスタンス最適pacアルゴリズム
• Authors: Zhaoqi Li, Lillian Ratliff, Houssam Nassif, Kevin Jamieson, Lalit Jain
• Abstract要約: この作業では、$(epsilon,delta)$-$textitPAC$設定における帯域幅の問題に焦点を当てます。 最良腕識別のための最小限の後悔最小化とインスタンス依存のPACを同時に行うアルゴリズムは存在しないことを示す。
• 参考スコア（独自算出の注目度）: 20.176752818200438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the stochastic contextual bandit setting, regret-minimizing algorithms have been extensively researched, but their instance-minimizing best-arm identification counterparts remain seldom studied. In this work, we focus on the stochastic bandit problem in the $(\epsilon,\delta)$-$\textit{PAC}$ setting: given a policy class $\Pi$ the goal of the learner is to return a policy $\pi\in \Pi$ whose expected reward is within $\epsilon$ of the optimal policy with probability greater than $1-\delta$. We characterize the first $\textit{instance-dependent}$ PAC sample complexity of contextual bandits through a quantity $\rho_{\Pi}$, and provide matching upper and lower bounds in terms of $\rho_{\Pi}$ for the agnostic and linear contextual best-arm identification settings. We show that no algorithm can be simultaneously minimax-optimal for regret minimization and instance-dependent PAC for best-arm identification. Our main result is a new instance-optimal and computationally efficient algorithm that relies on a polynomial number of calls to an argmax oracle.
• Abstract（参考訳）: 確率的文脈的バンディット設定では、後悔最小化アルゴリズムは広範囲に研究されてきたが、そのインスタンス最小化最善腕識別アルゴリズムはほとんど研究されていない。 この研究では、(\epsilon,\delta)$-$\textit{PAC}$設定における確率的バンディット問題に焦点をあてる: ポリシークラス$\Pi$を与えられた場合、学習者のゴールはポリシーを返却することである: $\pi\in \Pi$。 我々は、最初の$\textit{instance-dependent}$ PACサンプルの複雑さを$\rho_{\Pi}$で特徴づけ、Agnostic and linear contextual best-arm identification settingsに対して$\rho_{\Pi}$で一致した上と下の境界を提供する。 最良腕識別のための最小最小化とインスタンス依存PACを同時に行うアルゴリズムは存在しない。 我々の主な成果は、argmaxオラクルへの多項式数に依存する新しいインスタンス最適化および計算効率のアルゴリズムである。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。 ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。 我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
  論文  参考訳（メタデータ） (2023-02-07T02:22:31Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
  ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。 我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-13T10:54:52Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)

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

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