論文の概要: Exploration-Exploitation in Constrained MDPs
- arxiv url: http://arxiv.org/abs/2003.02189v1
- Date: Wed, 4 Mar 2020 17:03:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-26 12:22:55.309721
- Title: Exploration-Exploitation in Constrained MDPs
- Title(参考訳): 拘束型MDPの探査・探査
- Authors: Yonathan Efroni and Shie Mannor and Matteo Pirotta
- Abstract要約: 拘束マルコフ決定過程(CMDP)における探索・探索ジレンマについて検討する。
未知のCMDPで学習している間、エージェントは、MDPに関する新しい情報を見つけるために、トレードオフ探索を行う必要がある。
エージェントは最終的に良い方針や最適な方針を学習するが、学習プロセス中にエージェントが制約に過度に違反することを望まない。
- 参考スコア(独自算出の注目度): 79.23623305214275
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In many sequential decision-making problems, the goal is to optimize a
utility function while satisfying a set of constraints on different utilities.
This learning problem is formalized through Constrained Markov Decision
Processes (CMDPs). In this paper, we investigate the exploration-exploitation
dilemma in CMDPs. While learning in an unknown CMDP, an agent should trade-off
exploration to discover new information about the MDP, and exploitation of the
current knowledge to maximize the reward while satisfying the constraints.
While the agent will eventually learn a good or optimal policy, we do not want
the agent to violate the constraints too often during the learning process. In
this work, we analyze two approaches for learning in CMDPs. The first approach
leverages the linear formulation of CMDP to perform optimistic planning at each
episode. The second approach leverages the dual formulation (or saddle-point
formulation) of CMDP to perform incremental, optimistic updates of the primal
and dual variables. We show that both achieves sublinear regret w.r.t.\ the
main utility while having a sublinear regret on the constraint violations. That
being said, we highlight a crucial difference between the two approaches; the
linear programming approach results in stronger guarantees than in the dual
formulation based approach.
- Abstract(参考訳): 多くの逐次的な意思決定問題において、目的は異なるユーティリティに対する一連の制約を満たしながら、ユーティリティ機能を最適化することである。
この学習問題は制約付きマルコフ決定プロセス(cmdps)によって形式化される。
本稿では,CMDPの探査・探査ジレンマについて検討する。
未知のCMDPで学びながら、エージェントは、MDPに関する新たな情報を見つけるためにトレードオフ探索を行い、現在の知識を活用して、制約を満たしながら報酬を最大化するべきである。
エージェントは最終的に良い方針や最適な方針を学習するが、学習プロセス中にエージェントが制約に過度に違反することを望まない。
本研究では,cmdpsで学習する2つのアプローチを分析した。
第1のアプローチはCMDPの線形定式化を利用して各エピソードで楽観的な計画を行う。
第二のアプローチはCMDPの双対定式化(サドル点定式化)を利用して、原始変数と双対変数の漸進的で楽観的な更新を行う。
いずれも,制約違反をサブ線形後悔しながら,主効用としてサブ線形後悔を実現することを示す。
とはいえ、線形プログラミングアプローチは、双対の定式化に基づくアプローチよりも強い保証をもたらす。
関連論文リスト
- Two-Stage ML-Guided Decision Rules for Sequential Decision Making under Uncertainty [55.06411438416805]
SDMU (Sequential Decision Making Under Uncertainty) は、エネルギー、金融、サプライチェーンといった多くの領域において、ユビキタスである。
いくつかのSDMUは、自然にマルチステージ問題(MSP)としてモデル化されているが、結果として得られる最適化は、計算の観点からは明らかに困難である。
本稿では,2段階の一般決定規則(TS-GDR)を導入し,線形関数を超えて政策空間を一般化する手法を提案する。
TS-GDRの有効性は、TS-LDR(Two-Stage Deep Decision Rules)と呼ばれるディープリカレントニューラルネットワークを用いたインスタンス化によって実証される。
論文 参考訳(メタデータ) (2024-05-23T18:19:47Z) - Reward-Punishment Reinforcement Learning with Maximum Entropy [3.123049150077741]
本稿では,長期政策エントロピーの最適化と報奨助成強化学習の目的を統合するソフトなDeep MaxPain'(SoftDMP)アルゴリズムを提案する。
我々のモチベーションは、従来の max' および min' 演算子を超えたアクション値の更新に使用される演算子のよりスムーズなバリエーションを促進することである。
論文 参考訳(メタデータ) (2024-05-20T05:05:14Z) - Learning Adversarial MDPs with Stochastic Hard Constraints [37.24692425018]
本研究では,制約付き意思決定プロセスにおけるオンライン学習問題について,対向的損失と厳しい制約を伴う検討を行った。
我々は,各エピソードの制約を高い確率で満たしながら,サブ線形後悔を実現するアルゴリズムを設計する。
論文 参考訳(メタデータ) (2024-03-06T12:49:08Z) - Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。
提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
論文 参考訳(メタデータ) (2024-02-24T09:47:46Z) - Model-based Constrained MDP for Budget Allocation in Sequential
Incentive Marketing [28.395877073390434]
逐次インセンティブマーケティングは、オンラインビジネスにとって顧客を獲得し、忠誠心を高め、売上を伸ばすための重要なアプローチである。
予算制約下でのリターンを最大化するインセンティブを効果的に割り当てる方法については、文献ではあまり研究されていない。
本稿では,2項探索とモデルベース計画を組み合わせた効率的な学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-02T08:10:45Z) - Safe Exploration by Solving Early Terminated MDP [77.10563395197045]
我々は、Early TerminatedP(ET-MDP)の枠組みの下で、安全なRL問題に対処する新しいアプローチを導入する。
まず、ET-MDPを対応するCMDPと同じ最適値関数を持つ非制約アルゴリズムとして定義する。
そこで,文脈モデルに基づく非政治アルゴリズムを提案し,ET-MDPを解き,それに対応するCMDPをより良い性能で解き,学習効率を向上する。
論文 参考訳(メタデータ) (2021-07-09T04:24:40Z) - Learning MDPs from Features: Predict-Then-Optimize for Sequential
Decision Problems by Reinforcement Learning [52.74071439183113]
我々は、強化学習を通して解決された逐次決定問題(MDP)の文脈における予測列最適化フレームワークについて検討した。
2つの重要な計算課題は、意思決定中心の学習をMDPに適用することである。
論文 参考訳(メタデータ) (2021-06-06T23:53:31Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳(メタデータ) (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。