論文の概要: Quantum Algorithms for Reinforcement Learning with a Generative Model
- arxiv url: http://arxiv.org/abs/2112.08451v1
- Date: Wed, 15 Dec 2021 19:51:49 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-26 14:13:47.359716
- Title: Quantum Algorithms for Reinforcement Learning with a Generative Model
- Title（参考訳）: 生成モデルを用いた強化学習のための量子アルゴリズム
- Authors: Daochen Wang, Aarthi Sundaram, Robin Kothari, Ashish Kapoor, Martin
Roetteler
- Abstract要約: 強化学習は、エージェントがその累積報酬を最大化するために環境とどのように相互作用するかを研究する。
最適ポリシー(pi*$)、最適値関数(v*$)、最適値関数(q*$)を近似する量子アルゴリズムを設計する。
一致する量子下界を証明して、q*$を計算するための量子アルゴリズムが最適であることを示す。
- 参考スコア（独自算出の注目度）: 16.168901236223117
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Reinforcement learning studies how an agent should interact with an
environment to maximize its cumulative reward. A standard way to study this
question abstractly is to ask how many samples an agent needs from the
environment to learn an optimal policy for a $\gamma$-discounted Markov
decision process (MDP). For such an MDP, we design quantum algorithms that
approximate an optimal policy ($\pi^*$), the optimal value function ($v^*$),
and the optimal $Q$-function ($q^*$), assuming the algorithms can access
samples from the environment in quantum superposition. This assumption is
justified whenever there exists a simulator for the environment; for example,
if the environment is a video game or some other program. Our quantum
algorithms, inspired by value iteration, achieve quadratic speedups over the
best-possible classical sample complexities in the approximation accuracy
($\epsilon$) and two main parameters of the MDP: the effective time horizon
($\frac{1}{1-\gamma}$) and the size of the action space ($A$). Moreover, we
show that our quantum algorithm for computing $q^*$ is optimal by proving a
matching quantum lower bound.
- Abstract（参考訳）: 強化学習は、エージェントがその累積報酬を最大化する環境とどのように相互作用すべきかを研究する。
この問題を抽象的に研究する標準的な方法は、エージェントが環境から必要とするサンプル数を問うことで、$\gamma$-discounted Markov decision process (MDP) の最適なポリシーを学ぶことである。
このようなMDPに対して、アルゴリズムが量子重ね合わせの環境からサンプルにアクセスできると仮定して、最適なポリシー(\pi^*$)、最適な値関数(v^*$)、最適な$Q$-function(q^*$)を近似する量子アルゴリズムを設計する。
この仮定は、例えば、環境がビデオゲームや他のプログラムである場合、環境のシミュレータが存在するときに正当化される。
私たちの量子アルゴリズムは、値の反復に触発され、近似精度(\epsilon$)とmdpの2つの主要なパラメータ(有効時間軸(\frac{1}{1-\gamma}$)と作用空間のサイズ(a$)で、最も考えられる古典的サンプルの複雑さよりも2倍のスピードアップを達成します。
さらに,$q^*$ を計算するための量子アルゴリズムは,一致する量子下限を証明すれば最適であることを示す。
関連論文リスト
- 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) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳（メタデータ） (2023-03-17T17:53:28Z) - A Quadratic Speedup in the Optimization of Noisy Quantum Optical
Circuits [5.074606924176912]
光子数分解(PNR)検出器を用いた線形光量子回路は、ガウスボソンサンプリング(GBS)とゴッテマン・キタエフ・プレスキル(GKP)のような非ガウス状態の準備の両方に使用される。
本稿では,回路パラメトリゼーションに関する検出確率,条件状態,およびそれらの勾配を計算するアルゴリズム群を紹介する。
これらのアルゴリズムは、オープンソースのフォトニック最適化ライブラリMrMustardで実装され、使用可能である。
論文 参考訳（メタデータ） (2023-03-15T18:51:36Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - The Quantum Approximate Optimization Algorithm performance with low
entanglement and high circuit depth [0.0]
変分量子アルゴリズムは、現在の雑音量子コンピュータを使用する最も広範な方法の1つである。
最適化問題の解法における絡み合いの役割について検討する。
ここでは, 絡み合いが MaxCut と Exact Cover 3 問題において軽微な役割を担っていると結論づける。
論文 参考訳（メタデータ） (2022-07-07T16:21:36Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-26T22:09:59Z) - Variational Quantum Algorithms for Semidefinite Programming [3.481985817302898]
半定値プログラム(SDP)は、操作研究、最適化、量子情報科学などにおける凸最適化問題である。
本稿では,SDPを近似的に解くための変分量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-16T13:10:48Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Operator Sampling for Shot-frugal Optimization in Variational Algorithms [0.860968116787044]
本稿では,H = sum_i c_i h_i$ からランダムサンプリング演算子 $h_i$ を用いて測定回数(ショット)を減らす方法を提案する。
我々は、量子ハードウェアノイズを伴わずに、分子H$、LiH、BeH$の基底状態を見つけるために、これや他のサンプリングを実装し、ほとんどの場合、ロザリンは他のサンプリングよりも優れている。
論文 参考訳（メタデータ） (2020-04-14T01:00:07Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。