論文の概要: Exploring and Learning in Sparse Linear MDPs without Computationally
Intractable Oracles
- arxiv url: http://arxiv.org/abs/2309.09457v2
- Date: Tue, 19 Sep 2023 01:56:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-20 10:58:11.359376
- Title: Exploring and Learning in Sparse Linear MDPs without Computationally
Intractable Oracles
- Title（参考訳）: 計算難解なOracleのない疎線形MDPの探索と学習
- Authors: Noah Golowich and Ankur Moitra and Dhruv Rohatgi
- Abstract要約: 本稿では,特徴選択の観点から線形MDPを再考する。
我々の主な成果は、この問題に対する最初のアルゴリズムである。
コンベックスプログラミングによって効率よく計算できることを示す。
- 参考スコア（独自算出の注目度）: 39.10180309328293
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The key assumption underlying linear Markov Decision Processes (MDPs) is that
the learner has access to a known feature map $\phi(x, a)$ that maps
state-action pairs to $d$-dimensional vectors, and that the rewards and
transitions are linear functions in this representation. But where do these
features come from? In the absence of expert domain knowledge, a tempting
strategy is to use the ``kitchen sink" approach and hope that the true features
are included in a much larger set of potential features. In this paper we
revisit linear MDPs from the perspective of feature selection. In a $k$-sparse
linear MDP, there is an unknown subset $S \subset [d]$ of size $k$ containing
all the relevant features, and the goal is to learn a near-optimal policy in
only poly$(k,\log d)$ interactions with the environment. Our main result is the
first polynomial-time algorithm for this problem. In contrast, earlier works
either made prohibitively strong assumptions that obviated the need for
exploration, or required solving computationally intractable optimization
problems.
Along the way we introduce the notion of an emulator: a succinct approximate
representation of the transitions that suffices for computing certain Bellman
backups. Since linear MDPs are a non-parametric model, it is not even obvious
whether polynomial-sized emulators exist. We show that they do exist and can be
computed efficiently via convex programming.
As a corollary of our main result, we give an algorithm for learning a
near-optimal policy in block MDPs whose decoding function is a low-depth
decision tree; the algorithm runs in quasi-polynomial time and takes a
polynomial number of samples. This can be seen as a reinforcement learning
analogue of classic results in computational learning theory. Furthermore, it
gives a natural model where improving the sample complexity via representation
learning is computationally feasible.
- Abstract（参考訳）: 基本となる線形マルコフ決定プロセス(mdps)は、学習者が既知の特徴写像$\phi(x, a)$にアクセスでき、状態-作用対を$d$-次元ベクトルにマッピングし、報酬と遷移がこの表現の線形関数である、という仮定である。
しかし、これらの機能はどこから来るのか?
専門家のドメイン知識がなければ,‘kitchen sink’というアプローチを採用して,真の機能がもっと大きな機能セットに含まれていることを期待する,という誘惑的な戦略がある。
本稿では,線形mdpを特徴選択の観点から再検討する。
a $k$-sparse linear MDP には、すべての関連する特徴を含む未知のサブセット $S \subset [d]$ of size $k$ が存在し、その目標は、環境との相互作用をpoly$(k,\log d)$でのみ学習することである。
我々の主な結果は、この問題に対する最初の多項式時間アルゴリズムである。
対照的に、初期の研究は、探索の必要性を損なう、あるいは計算的に難解な最適化問題を解く必要のある、禁止的に強い仮定をした。
その過程で、あるベルマンバックアップを計算するのに十分である遷移の簡潔な近似表現であるエミュレータの概念を導入する。
線形 MDP は非パラメトリックモデルであるため、多項式サイズのエミュレータが存在するかどうかさえ明らかではない。
それらは存在し、凸プログラミングによって効率的に計算できることを示す。
そこで本研究では,ブロック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) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Exponential Hardness of Reinforcement Learning with Linear Function
Approximation [20.066210529358177]
指数時間仮説に基づく線形強化学習において,特徴・地平線で指数関数的な計算下界を示す。
また、地平線依存に最適化された下界が$exp(sqrtH)$の最もよく知られた上界とほぼ一致することを示す。
論文 参考訳（メタデータ） (2023-02-25T00:19:49Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Online learning in MDPs with linear function approximation and bandit
feedback [13.32560004325655]
我々は,学習者がマルコフ決定プロセスと一連のエピソードで対話するオンライン学習問題を考える。
我々は, MDP-LinExp3 が, この問題設定のための最初の証明可能なアルゴリズムであることを示す。
論文 参考訳（メタデータ） (2020-07-03T11:06:38Z) - Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-23T17:08:54Z) - Learning Polynomials of Few Relevant Dimensions [12.122488725065388]
多項式回帰は学習と統計の基本的な原始である。
およそ$N = O_r,d(n log2(1/epsilon) (log n)d)$と$O_r,d(N n2)$である。
論文 参考訳（メタデータ） (2020-04-28T18:00:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。