論文の概要: Online Reinforcement Learning in Markov Decision Process Using Linear Programming

• arxiv url: http://arxiv.org/abs/2304.00155v1
• Date: Fri, 31 Mar 2023 22:21:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-04 19:29:07.153546
• Title: Online Reinforcement Learning in Markov Decision Process Using Linear Programming
• Title（参考訳）: 線形プログラミングを用いたマルコフ決定過程におけるオンライン強化学習
• Authors: Vincent Leon, S. Rasoul Etesami
• Abstract要約: マルコフ決定過程(MDP)におけるオンライン強化学習について検討した。 高確率で $tildeO(LXsqrtTA)$ regret を実現する,シンプルで効率的なモデルベースアルゴリズムを考案する。
• 参考スコア（独自算出の注目度）: 2.132096006921048
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider online reinforcement learning in episodic Markov decision process (MDP) with an unknown transition matrix and stochastic rewards drawn from a fixed but unknown distribution. The learner aims to learn the optimal policy and minimize their regret over a finite time horizon through interacting with the environment. We devise a simple and efficient model-based algorithm that achieves $\tilde{O}(LX\sqrt{TA})$ regret with high probability, where $L$ is the episode length, $T$ is the number of episodes, and $X$ and $A$ are the cardinalities of the state space and the action space, respectively. The proposed algorithm, which is based on the concept of "optimism in the face of uncertainty", maintains confidence sets of transition and reward functions and uses occupancy measures to connect the online MDP with linear programming. It achieves a tighter regret bound compared to the existing works that use a similar confidence sets framework and improves the computational effort compared to those that use a different framework but with a slightly tighter regret bound.
• Abstract（参考訳）: 我々は,未知の遷移行列と確率的報酬が固定的だが未知の分布から引き出されるエピソディックマルコフ決定過程(mdp)におけるオンライン強化学習を考える。 学習者は,環境との相互作用を通じて,最適方針を学習し,その後悔を最小限に抑えることを目的としている。 我々は、l$がエピソード長、$t$がエピソード数、$x$と$a$がそれぞれ状態空間とアクション空間の基数である高確率で$\tilde{o}(lx\sqrt{ta})$ regretを達成する、単純で効率的なモデルベースのアルゴリズムを考案する。 提案手法は「不確実性に直面した最適化」の概念に基づいており、遷移関数と報酬関数の信頼セットを維持し、オンラインmdpと線形プログラミングをつなぐために占有測度を用いる。 これは、同様の信頼セットフレームワークを使用している既存の作品と比較して、より厳しい後悔の束縛を達成し、異なるフレームワークを使用しているが、少し厳しい後悔の束縛を持つものよりも計算の労力を改善する。

関連論文リスト

• Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
  本研究は,完全情報フィードバックの下で,相変わらずの相変わらずの線形混合MDPについて検討した。 本稿では,占領率に基づく手法と政策に基づく手法の利点を組み合わせた新しいアルゴリズムを提案する。 我々のアルゴリズムは$widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, ここで$d$は特徴次元である。
  論文  参考訳（メタデータ） (2024-11-05T13:55:52Z)
• Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
  本稿では,次数$tildemathcalO(mathrmpoly(H)sqrtSAT)$の残差を求めるアルゴリズムを提案する。 提案したアルゴリズムと分析は、占有対策によって与えられる典型的なツールを完全に回避する。
  論文  参考訳（メタデータ） (2024-07-08T08:06:45Z)
• 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 Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• Efficient Learning in Non-Stationary Linear Markov Decision Processes [17.296084954104415]
  非定常線形(低ランク)マルコフ決定過程(MDP)におけるエピソード強化学習の研究 OPT-WLSVI は最小二乗の重み付け値に基づく楽観的なモデルフリーのアルゴリズムであり、指数重み付けを用いて過去のデータをスムーズに忘れる。 我々のアルゴリズムは、各時点で最高のポリシーと競合するときに、$d$$$widetildemathcalO(d5/4H2 Delta1/4 K3/4)$で上限付けられた後悔を実現する。
  論文  参考訳（メタデータ） (2020-10-24T11:02:45Z)
• 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)
• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret [44.374427255708135]
  無限水平平均逆マルコフ決定過程(MDP)のモデルフリーアルゴリズムである探索強化Q-ラーニング(EE-QL)を提案する。 EE-QLは、最適平均報酬のオンライン集中近似が利用可能であると仮定する。 これは、エルゴード的な仮定なしに$O(sqrt T)$後悔を達成する最初のモデル自由学習アルゴリズムであり、対数的因子を除いて、下位境界の$T$と一致する。
  論文  参考訳（メタデータ） (2020-06-08T05:09:32Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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