論文の概要: Navigating to the Best Policy in Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2106.02847v1
• Date: Sat, 5 Jun 2021 09:16:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2021-06-08 18:36:48.063690
• Title: Navigating to the Best Policy in Markov Decision Processes
• Title（参考訳）: マルコフ決定プロセスにおけるベストポリシーへの道
• Authors: Aymen Al Marjani, Aur\'elien Garivier, Alexandre Proutiere
• Abstract要約: マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
• 参考スコア（独自算出の注目度）: 68.8204255655161
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the classical active pure exploration problem in Markov Decision Processes, where the agent sequentially selects actions and, from the resulting system trajectory, aims at identifying the best policy as fast as possible. We propose an information-theoretic lower bound on the average number of steps required before a correct answer can be given with probability at least $1-\delta$. This lower bound involves a non-convex optimization problem, for which we propose a convex relaxation. We further provide an algorithm whose sample complexity matches the relaxed lower bound up to a factor $2$. This algorithm addresses general communicating MDPs; we propose a variant with reduced exploration rate (and hence faster convergence) under an additional ergodicity assumption. This work extends previous results relative to the \emph{generative setting}~\cite{marjani2020adaptive}, where the agent could at each step observe the random outcome of any (state, action) pair. In contrast, we show here how to deal with the \emph{navigation constraints}. Our analysis relies on an ergodic theorem for non-homogeneous Markov chains which we consider of wide interest in the analysis of Markov Decision Processes.
• Abstract（参考訳）: マルコフ決定過程における古典的能動純粋探索問題について検討し、エージェントが順次行動を選択し、結果の系軌道から可能な限り早く最良の政策を特定することを目的とする。 正解が少なくとも1〜\delta$の確率で与えられるまでに必要な平均ステップ数について,情報理論的な下限を提案する。 この下界には非凸最適化問題があり、そこでは凸緩和を提案する。 さらに、サンプルの複雑さが緩和された下界と2ドルの係数に一致するアルゴリズムを提供する。 本アルゴリズムは一般通信mdpに対処し,追加のエルゴディシティ仮定の下で探索速度(従って収束速度)を低減した変種を提案する。 この研究は、エージェントが各ステップで任意の(状態、動作)ペアのランダムな結果を見ることができるような、\emph{generative setting}~\cite{marjani2020adaptive}に対する以前の結果を拡張する。 対照的に、ここでは \emph{navigation constraints} を扱う方法を示す。 我々の解析は、マルコフ決定過程の解析に広く関心を持つと考える非同次マルコフ連鎖に対するエルゴード定理に依存している。

関連論文リスト

• Performative Reinforcement Learning with Linear Markov Decision Process [14.75815792682734]
  提案手法がマルコフ決定過程の報酬と遷移の両方に影響を及ぼすような表現的強化学習の設定について検討する。 大規模MDPの主要な理論モデルであるEmphlinear Markov決定過程を一般化する。
  論文  参考訳（メタデータ） (2024-11-07T23:04:48Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• Contextual Decision-Making with Knapsacks Beyond the Worst Case [5.65888994172721]
  資源制約を伴う動的意思決定シナリオの枠組みについて検討する。 このフレームワークでは、エージェントがランダムな要求を観察すると、各ラウンドでアクションを選択する。 我々のアルゴリズムは最悪の場合であっても、ほぼ最適の$widetildeO(sqrtT)$ regretを維持していることを証明している。
  論文  参考訳（メタデータ） (2022-11-25T08:21:50Z)
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm [4.932130498861987]
  重要度サンプリングに基づく自然アクタ-クリティック(nac)アルゴリズムのオフポリシー変種に対する有限サンプル収束保証を提供する。 このアルゴリズムは、ステップの適切な選択の下で$mathcalo(epsilon-3log2(1/epsilon)$のサンプル複雑性を持つ大域的最適ポリシーに収束する。
  論文  参考訳（メタデータ） (2021-02-18T13:22:59Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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