論文の概要: Causal Markov Decision Processes: Learning Good Interventions
Efficiently
- arxiv url: http://arxiv.org/abs/2102.07663v1
- Date: Mon, 15 Feb 2021 16:48:54 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-16 16:03:34.331735
- Title: Causal Markov Decision Processes: Learning Good Interventions
Efficiently
- Title（参考訳）: 因果マルコフ決定プロセス:良い介入を効率的に学ぶ
- Authors: Yangyi Lu, Amirhossein Meisami, Ambuj Tewari
- Abstract要約: 連続的な意思決定のための新しい形式主義である因果マルコフ決定プロセス(C-MDPs)を紹介します。
デジタルヘルスケアやデジタルマーケティングなどの現代および新興のアプリケーション分野は、C-MDPによるモデリングの恩恵を受けることができます。
- 参考スコア（独自算出の注目度）: 24.58691421788476
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce causal Markov Decision Processes (C-MDPs), a new formalism for
sequential decision making which combines the standard MDP formulation with
causal structures over state transition and reward functions. Many contemporary
and emerging application areas such as digital healthcare and digital marketing
can benefit from modeling with C-MDPs due to the causal mechanisms underlying
the relationship between interventions and states/rewards. We propose the
causal upper confidence bound value iteration (C-UCBVI) algorithm that exploits
the causal structure in C-MDPs and improves the performance of standard
reinforcement learning algorithms that do not take causal knowledge into
account. We prove that C-UCBVI satisfies an $\tilde{O}(HS\sqrt{ZT})$ regret
bound, where $T$ is the the total time steps, $H$ is the episodic horizon, and
$S$ is the cardinality of the state space. Notably, our regret bound does not
scale with the size of actions/interventions ($A$), but only scales with a
causal graph dependent quantity $Z$ which can be exponentially smaller than
$A$. By extending C-UCBVI to the factored MDP setting, we propose the causal
factored UCBVI (CF-UCBVI) algorithm, which further reduces the regret
exponentially in terms of $S$. Furthermore, we show that RL algorithms for
linear MDP problems can also be incorporated in C-MDPs. We empirically show the
benefit of our causal approaches in various settings to validate our algorithms
and theoretical results.
- Abstract（参考訳）: C-MDP(Causal Markov Decision Process)は、標準的なMDPの定式化と、状態遷移と報酬関数に関する因果構造を組み合わせた、シーケンシャルな意思決定の新しい形式である。
デジタルヘルスケアやデジタルマーケティングなどの現代および新興のアプリケーション分野は、介入と状態/報酬の関係の基礎となる因果機構のために、C-MDPによるモデリングの恩恵を受けることができます。
C-MDPの因果構造を利用し、因果知識を考慮に入れない標準強化学習アルゴリズムの性能を向上させる因果的高信頼境界値反復(C-UCBVI)アルゴリズムを提案する。
我々は、C-UCBVI が $\tilde{O}(HS\sqrt{ZT})$ 後悔境界を満たすことを証明している。ここでは、$T$ は総時間ステップ、$H$ はエピソド地平線、$S$ は状態空間のカーディナリティである。
特に、我々の後悔の束縛はアクション/インターベンションのサイズ(A$)でスケールしないが、因果グラフ依存量$Z$でのみスケールし、これは指数的に$A$より小さい。
C-UCBVI をファクタリング MDP 設定に拡張することにより, 因果的ファクタリング UCBVI (CF-UCBVI) アルゴリズムを提案する。
さらに,線形MDP問題に対するRLアルゴリズムもC-MDPに組み込むことができることを示す。
我々のアルゴリズムと理論的結果を検証するための様々な設定における因果的アプローチの利点を実証的に示す。
関連論文リスト
- Monte Carlo Planning for Stochastic Control on Constrained Markov Decision Processes [1.445706856497821]
本研究は,MDP フレームワークである textttSD-MDP を定義し,MDP の遷移と報酬ダイナミクスの因果構造を解析する。
モンテカルロサンプリングから独立な値推定を行うことにより、最適ポリシの下での値関数の推定誤差に関する理論的保証を導出する。
論文 参考訳（メタデータ） (2024-06-23T16:22:40Z) - Settling Constant Regrets in Linear Markov Decision Processes [57.34287648914407]
強化学習(RL)における絶え間ない後悔の保証について検討する。
我々は不特定線形マルコフ決定過程(MDP)に対するアルゴリズムCert-LSVI-UCBを導入する。
Cert-LSVI-UCB は $tildemathcalO(d3H5/Delta)$ の累積後悔と高い確率を持つ MDP に対して、$zeta$ が $tildemathcalO(Delta / (sqrtd) 以下であることを仮定する。
論文 参考訳（メタデータ） (2024-04-16T17:23:19Z) - Provably Efficient CVaR RL in Low-rank MDPs [58.58570425202862]
リスクに敏感な強化学習(RL)について検討する。
本稿では, CVaR RLにおける探索, 搾取, 表現学習の相互作用のバランスをとるための, 新たなアッパー信頼境界(UCB)ボーナス駆動アルゴリズムを提案する。
提案アルゴリズムは,各エピソードの長さが$H$,アクション空間が$A$,表現の次元が$d$であるような,エプシロン$最適CVaRのサンプル複雑性を実現する。
論文 参考訳（メタデータ） (2023-11-20T17:44:40Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳（メタデータ） (2023-07-01T18:35:21Z) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-24T13:46:09Z) - Improved Exploration in Factored Average-Reward MDPs [23.096751699592133]
我々は、未知の因子マルコフ決定過程(FMDP)における平均回帰基準の下での後悔の最小化タスクを考える。
我々は、遷移関数の個々の要素に対して定義されたバーンスタイン型信頼集合に依存する、DBN-UCRLと呼ばれる人気のあるUCRL2戦略にインスパイアされた、新しい後悔の最小化戦略を導入する。
本稿では,DBN-UCRL は,一般的な因子分解構造において,$mathcal S_i$'s の大きさとそれに関連する直径関連項の依存性から,既存の後悔境界よりも厳格に改善された後悔境界を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-09T21:15:01Z) - Efficient Reinforcement Learning in Factored MDPs with Application to
Constrained RL [25.119552984253882]
マルコフ決定過程(FMDP)における強化学習について検討した。
本稿では,FMDPの分解構造を利用したFMDP-BFアルゴリズムを提案する。
応用として,knapsack 制約付き RL (RLwK) と呼ばれる制約付き RL の新しい定式化について検討する。
論文 参考訳（メタデータ） (2020-08-31T02:20:41Z) - 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) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z) - Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and
Tighter Regret Bounds for the Non-Episodic Setting [24.90164851620799]
非等化因子マルコフ決定過程(FMDP)における強化学習の研究
FMDPに対する2つの近似およびオラクル効率アルゴリズムを提案する。
我々のオラクル効率のアルゴリズムは、コンピュータネットワーク管理シミュレーションにおいて、これまで提案されていた近似アルゴリズムよりも優れていた。
論文 参考訳（メタデータ） (2020-02-06T15:19:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。