論文の概要: Bayesian Learning of Optimal Policies in Markov Decision Processes with
Countably Infinite State-Space
- arxiv url: http://arxiv.org/abs/2306.02574v2
- Date: Wed, 7 Feb 2024 21:52:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-10 03:18:49.386538
- Title: Bayesian Learning of Optimal Policies in Markov Decision Processes with
Countably Infinite State-Space
- Title（参考訳）: 可算無限状態空間を持つマルコフ決定過程における最適政策のベイズ学習
- Authors: Saghar Adler, Vijay Subramanian
- Abstract要約: 離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。
動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。
提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Models of many real-life applications, such as queuing models of
communication networks or computing systems, have a countably infinite
state-space. Algorithmic and learning procedures that have been developed to
produce optimal policies mainly focus on finite state settings, and do not
directly apply to these models. To overcome this lacuna, in this work we study
the problem of optimal control of a family of discrete-time countable
state-space Markov Decision Processes (MDPs) governed by an unknown parameter
$\theta\in\Theta$, and defined on a countably-infinite state space $\mathcal
X=\mathbb{Z}_+^d$, with finite action space $\mathcal A$, and an unbounded cost
function. We take a Bayesian perspective with the random unknown parameter
$\boldsymbol{\theta}^*$ generated via a given fixed prior distribution on
$\Theta$. To optimally control the unknown MDP, we propose an algorithm based
on Thompson sampling with dynamically-sized episodes: at the beginning of each
episode, the posterior distribution formed via Bayes' rule is used to produce a
parameter estimate, which then decides the policy applied during the episode.
To ensure the stability of the Markov chain obtained by following the policy
chosen for each parameter, we impose ergodicity assumptions. From this
condition and using the solution of the average cost Bellman equation, we
establish an $\tilde O(dh^d\sqrt{|\mathcal A|T})$ upper bound on the Bayesian
regret of our algorithm, where $T$ is the time-horizon. Finally, to elucidate
the applicability of our algorithm, we consider two different queuing models
with unknown dynamics, and show that our algorithm can be applied to develop
approximately optimal control algorithms.
- Abstract（参考訳）: 通信ネットワークやコンピュータシステムのキューイングモデルなど、多くの実世界のアプリケーションモデルは、数え切れないほど無限の状態空間を持つ。
最適ポリシーを生成するために開発されたアルゴリズムおよび学習手順は、主に有限状態設定に焦点を当てており、これらのモデルに直接適用しない。
そこで本研究では,未知のパラメータ $\theta\in\theta$ によって制御される離散時間可算状態空間マルコフ決定過程(mdps)の群を最適制御し,有限作用空間 $\mathcal a$ と非有界コスト関数を持つ可算無限状態空間 $\mathcal x=\mathbb{z}_+^d$ 上で定義される問題について検討する。
与えられた固定事前分布で生成されるランダムな未知パラメータ $\boldsymbol{\theta}^*$ でベイズ的視点を取る。
未知のMDPを最適に制御するため,各エピソードの冒頭にベイズの規則によって形成された後続分布を用いてパラメータ推定を行い,そのエピソード中に適用されるポリシーを決定する。
各パラメータに選択されたポリシーに従って得られるマルコフ連鎖の安定性を確保するため、エルゴディシティ仮定を課す。
この条件と平均コストベルマン方程式の解を用いて、我々のアルゴリズムに対するベイズ的後悔の上に$\tilde O(dh^d\sqrt{|\mathcal A|T})$上界を定め、そこでは$T$が時間水平である。
最後に, 本アルゴリズムの適用性を明らかにするために, 未知ダイナミクスを持つ2つの異なるキューモデルを検討し, 最適制御アルゴリズムの開発に本アルゴリズムが適用可能であることを示す。
関連論文リスト
- Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。
提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
論文 参考訳（メタデータ） (2024-10-02T08:46:34Z) - Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。
私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
論文 参考訳（メタデータ） (2023-09-27T04:33:09Z) - 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) - Structural Estimation of Markov Decision Processes in High-Dimensional
State Space with Finite-Time Guarantees [39.287388288477096]
本研究では,実施行動と訪問状態の観測可能な履歴に基づいて,人間エージェントによる動的決定の構造モデルの推定作業を検討する。
この問題には固有のネスト構造があり、内部問題では与えられた報酬関数に対する最適ポリシーが特定され、外部問題では適合度の測定が最大化される。
本研究では,高次元状態空間を扱うための有限時間保証付き単一ループ推定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-04T00:11:38Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Efficient Policy Iteration for Robust Markov Decision Processes via
Regularization [49.05403412954533]
ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。
最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。
本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
論文 参考訳（メタデータ） (2022-05-28T04:05:20Z) - A Reinforcement Learning Approach to the Stochastic Cutting Stock
Problem [0.0]
本稿では,削減された無限水平決定プロセスとして,カットストック問題の定式化を提案する。
最適解は、各状態と決定を関連付け、期待される総コストを最小化するポリシーに対応する。
論文 参考訳（メタデータ） (2021-09-20T14:47:54Z) - Implicitly Regularized RL with Implicit Q-Values [42.87920755961722]
Q$関数は多くの強化学習(RL)アルゴリズムにおいて中心的な量であり、RLエージェントは(ソフト)グレーディポリシーに従って振る舞う。
対数政治と値関数の和として、暗黙的に$Q$-関数をパラメータ化することを提案する。
我々は,大規模アクション空間に適した実用的な非政治的深部RLアルゴリズムを導出し,ポリシーと$Q$値とのソフトマックス関係を強制する。
論文 参考訳（メタデータ） (2021-08-16T12:20:47Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳（メタデータ） (2020-01-27T03:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。