論文の概要: 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} を扱う方法を示す。 我々の解析は、マルコフ決定過程の解析に広く関心を持つと考える非同次マルコフ連鎖に対するエルゴード定理に依存している。

関連論文リスト

• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Regret Analysis of the Stochastic Direct Search Method for Blind Resource Allocation [0.0]
  雑音の存在下での線形制約および微分自由度最適化のための直接探索法(パターン探索)について検討した。 一般の場合、T2/3の次数に対する後悔の上限を与える。 我々の数学的分析は、決定論的で制約のないケースにおいて、副産物として、時間非依存の後悔境界を定めている。
  論文  参考訳（メタデータ） (2022-10-11T07:40:45Z)
• Markov Decision Process modeled with Bandits for Sequential Decision Making in Linear-flow [73.1896399783641]
  会員/加入者の獲得と保持では、複数のページを連続してマーケティングコンテンツを推奨する必要がある。 遷移確率行列をモデル化するためにBandits を用いた MDP としてこの問題を定式化することを提案する。 提案したMDPのBanditsアルゴリズムは,$epsilon$-greedyと$epsilon$-greedy,$epsilon$,IndependentBandits,InteractionBanditsでQ-learningを上回っている。
  論文  参考訳（メタデータ） (2021-07-01T03:54:36Z)
• 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)
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards [10.66048003460524]
  本稿では,複数の演奏とマルコフ報酬を含む古典的マルチアームバンディット問題の拡張について検討する。 この問題に対処するために、各段階において、全てのアームのサンプル手段からの情報と、ラウンドロビン方式で選択された単一アームのクルバック・リーバー上信頼境界とを結合する適応的アロケーションルールを検討する。
  論文  参考訳（メタデータ） (2020-01-30T08:09:01Z)

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

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