論文の概要: Online Resource Allocation in Episodic Markov Decision Processes
- arxiv url: http://arxiv.org/abs/2305.10744v2
- Date: Wed, 18 Oct 2023 05:34:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-19 13:09:14.228956
- Title: Online Resource Allocation in Episodic Markov Decision Processes
- Title（参考訳）: マルコフ決定過程におけるオンライン資源配分
- Authors: Duksang Lee, Dabeen Lee
- Abstract要約: 本稿では, 有限水平制約マルコフ決定過程におけるオンライン割当問題として, 問題を定式化する。
本稿では,観測・観測・観測・観測体制の整備と既存の決定・観測体制の改善について述べる。
平均報酬と平均資源消費関数にアクセスできる静的最適政策に対する後悔は、高い確率で$tilde O(rho-1H3/2SsqrtAT)$で束縛されていることを示す。
- 参考スコア（独自算出の注目度）: 2.1756081703276
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies a long-term resource allocation problem over multiple
periods where each period requires a multi-stage decision-making process. We
formulate the problem as an online allocation problem in an episodic
finite-horizon constrained Markov decision process with an unknown
non-stationary transition function and stochastic non-stationary reward and
resource consumption functions. We propose the observe-then-decide regime and
improve the existing decide-then-observe regime, while the two settings differ
in how the observations and feedback about the reward and resource consumption
functions are given to the decision-maker. We develop an online dual mirror
descent algorithm that achieves near-optimal regret bounds for both settings.
For the observe-then-decide regime, we prove that the expected regret against
the dynamic clairvoyant optimal policy is bounded by $\tilde
O(\rho^{-1}{H^{3/2}}S\sqrt{AT})$ where $\rho\in(0,1)$ is the budget parameter,
$H$ is the length of the horizon, $S$ and $A$ are the numbers of states and
actions, and $T$ is the number of episodes. For the decide-then-observe regime,
we show that the regret against the static optimal policy that has access to
the mean reward and mean resource consumption functions is bounded by $\tilde
O(\rho^{-1}{H^{3/2}}S\sqrt{AT})$ with high probability. We test the numerical
efficiency of our method for a variant of the resource-constrained inventory
management problem.
- Abstract（参考訳）: 本稿では,多段階意思決定プロセスを必要とする複数期間にわたる長期資源配分問題について検討する。
未知の非定常遷移関数と確率的非定常報酬と資源消費関数を持つエピソディック有限ホリゾン制約マルコフ決定過程において、オンライン割り当て問題として問題を定式化する。
そこで,提案手法では,報酬と資源消費関数に関する観察とフィードバックが意思決定者に与えられる方法が異なるが,観察・決定方式を提案し,既存の決定・監視体制を改善する。
両設定のほぼ最適後悔境界を実現するオンライン二重ミラー降下アルゴリズムを開発した。
オブザーバ・then-decide 体制では、動的透視的最適ポリシーに対する期待された後悔が $\tilde O(\rho^{-1}{H^{3/2}}S\sqrt{AT})$ で有界であることが証明され、$\rho\in(0,1)$ は予算パラメータ、$H$ は地平線の長さ、$S$ と $A$ は状態と行動の数、$T$ はエピソード数である。
ここでは, 平均報酬と平均資源消費関数にアクセスできる静的最適政策に対する後悔は, 高確率で$\tilde O(\rho^{-1}{H^{3/2}}S\sqrt{AT})$で有界であることを示す。
資源制約のある在庫管理問題の変種に対して,本手法の数値効率を検証した。
関連論文リスト
- Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space [0.0]
離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。
動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。
提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
論文 参考訳（メタデータ） (2023-06-05T03:57:16Z) - 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) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳（メタデータ） (2022-12-12T21:37:36Z) - Double Thompson Sampling in Finite stochastic Games [10.559241770674724]
有限割引マルコフ決定プロセスの下での探索と利用のトレードオフ問題を考察する。
このような問題を解決するために、二重トンプソンサンプリング強化学習アルゴリズム(DTS)を提案する。
論文 参考訳（メタデータ） (2022-02-21T06:11:51Z) - Dynamic Planning and Learning under Recovering Rewards [18.829837839926956]
我々は「純粋周期ポリシー」のクラスの性能保証を提案し、構築し、証明する。
私たちのフレームワークとポリシー設計は、他のオフライン計画およびオンライン学習アプリケーションに適応する可能性がある。
論文 参考訳（メタデータ） (2021-06-28T15:40:07Z) - Minimax Regret for Stochastic Shortest Path [63.45407095296692]
我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
論文 参考訳（メタデータ） (2021-03-24T10:11:49Z) - Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
論文 参考訳（メタデータ） (2020-12-13T04:47:37Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。