論文の概要: Efficient Algorithms for Planning with Participation Constraints
- arxiv url: http://arxiv.org/abs/2205.07767v1
- Date: Mon, 16 May 2022 15:47:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-17 15:03:09.194878
- Title: Efficient Algorithms for Planning with Participation Constraints
- Title(参考訳): 参加制約を考慮した効率的な計画アルゴリズム
- Authors: Hanrui Zhang, Yu Cheng, Vincent Conitzer
- Abstract要約: 我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。
この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。
有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
- 参考スコア(独自算出の注目度): 74.74967476995572
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of planning with participation constraints introduced
in [Zhang et al., 2022]. In this problem, a principal chooses actions in a
Markov decision process, resulting in separate utilities for the principal and
the agent. However, the agent can and will choose to end the process whenever
his expected onward utility becomes negative. The principal seeks to compute
and commit to a policy that maximizes her expected utility, under the
constraint that the agent should always want to continue participating. We
provide the first polynomial-time exact algorithm for this problem for
finite-horizon settings, where previously only an additive
$\varepsilon$-approximation algorithm was known. Our approach can also be
extended to the (discounted) infinite-horizon case, for which we give an
algorithm that runs in time polynomial in the size of the input and
$\log(1/\varepsilon)$, and returns a policy that is optimal up to an additive
error of $\varepsilon$.
- Abstract(参考訳): 我々は,[zhang et al., 2022]に導入された参加制約による計画の問題を考える。
この問題では、プリンシパルがマルコフ決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。
しかし、エージェントは、期待する前向きの効用が負になるたびに、プロセスの終了を選択できる。
プリンシパルは、エージェントが常に参加し続けたいという制約の下で、彼女の期待するユーティリティを最大化するポリシーを計算し、コミットすることを目指している。
この問題に対する最初の多項式時間正確なアルゴリズムを有限水平設定に提供し、以前は加法$\varepsilon$-approximationアルゴリズムのみが知られていた。
このアプローチは、入力のサイズで時間多項式を実行するアルゴリズムと$\log(1/\varepsilon)$を与え、$\varepsilon$の加算誤差まで最適となるポリシーを返す(数え切れない)無限ホリゾンの場合にも拡張できる。
関連論文リスト
- Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳(メタデータ) (2023-02-22T20:21:25Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T14:37:21Z) - Learning Infinite-Horizon Average-Reward Markov Decision Processes with
Constraints [39.715977181666766]
本研究では,無限水平平均回帰マルコフ決定過程(MDP)のコスト制約による後悔について検討する。
我々のアルゴリズムはエルゴディックMDPに対して$widetildeO(sqrtT)$ regret and constant constraint violationを保証します。
これらは、MDPをコスト制約で弱い通信を行うための最初の証明可能なアルゴリズムである。
論文 参考訳(メタデータ) (2022-01-31T23:52:34Z) - Safe Online Bid Optimization with Return-On-Investment and Budget
Constraints subject to Uncertainty [87.81197574939355]
最適化問題と学習問題の両方について検討する。
我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。
より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
論文 参考訳(メタデータ) (2022-01-18T17:24:20Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Model-Free Algorithm and Regret Analysis for MDPs with Long-Term
Constraints [38.2783003051101]
本稿では,制約付き最適化とQ-ラーニングの概念を用いて,長期制約付きCMDPのアルゴリズムを提案する。
本研究は, 長期的制約を伴うMDPの遺残分析における最初の結果であり, 遷移確率はアプリオリではないことに留意する。
論文 参考訳(メタデータ) (2020-06-10T17:19:29Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。