論文の概要: Best Policy Identification in Linear MDPs
- arxiv url: http://arxiv.org/abs/2208.05633v1
- Date: Thu, 11 Aug 2022 04:12:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-12 12:54:20.374400
- Title: Best Policy Identification in Linear MDPs
- Title（参考訳）: 線形MDPにおける最適政策同定
- Authors: Jerome Taupin, Yassir Jedra, Alexandre Proutiere
- Abstract要約: 縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
- 参考スコア（独自算出の注目度）: 70.57916977441262
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of best policy identification in discounted linear
Markov Decision Processes in the fixed confidence setting under a generative
model. We first derive an instance-specific lower bound on the expected number
of samples required to identify an $\varepsilon$-optimal policy with
probability $1-\delta$. The lower bound characterizes the optimal sampling rule
as the solution of an intricate non-convex optimization program, but can be
used as the starting point to devise simple and near-optimal sampling rules and
algorithms. We devise such algorithms. One of these exhibits a sample
complexity upper bounded by ${\cal O}({\frac{d}{(\varepsilon+\Delta)^2}}
(\log(\frac{1}{\delta})+d))$ where $\Delta$ denotes the minimum reward gap of
sub-optimal actions and $d$ is the dimension of the feature space. This upper
bound holds in the moderate-confidence regime (i.e., for all $\delta$), and
matches existing minimax and gap-dependent lower bounds. We extend our
algorithm to episodic linear MDPs.
- Abstract（参考訳）: 縮退した線形マルコフ決定過程における最適政策識別の問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
まず,$\varepsilon$-optimal ポリシを 1-\delta$ の確率で識別するために必要なサンプル数の,インスタンス固有の下限を導出する。
下限は、複雑な非凸最適化プログラムの解として最適なサンプリングルールを特徴づけるが、単純で準最適サンプリングルールとアルゴリズムを考案するための出発点として使用できる。
このようなアルゴリズムを考案する。
これらのうちの1つは、${\cal o}({\frac{d}{(\varepsilon+\delta)^2}} (\log(\frac{1}{\delta})+d)$ ここで$\delta$は副最適作用の最小報酬ギャップを表し、$d$は特徴空間の次元である。
この上限は、中程度信頼体制(すなわちすべての$\delta$)にあり、既存のミニマックスとギャップ依存の下位境界と一致する。
我々はこのアルゴリズムを線形MDPに拡張する。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - 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) - Sharper Model-free Reinforcement Learning for Average-reward Markov
Decision Processes [21.77276136591518]
我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。
シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
論文 参考訳（メタデータ） (2023-06-28T17:43:19Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Instance-optimal PAC Algorithms for Contextual Bandits [20.176752818200438]
この作業では、$(epsilon,delta)$-$textitPAC$設定における帯域幅の問題に焦点を当てます。
最良腕識別のための最小限の後悔最小化とインスタンス依存のPACを同時に行うアルゴリズムは存在しないことを示す。
論文 参考訳（メタデータ） (2022-07-05T23:19:43Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed
Distributions [2.2940141855172036]
我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。
$delta$-correctアルゴリズムの下位境界はよく知られている。
我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
論文 参考訳（メタデータ） (2019-08-24T05:31:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。