論文の概要: Online Resource Allocation in Episodic Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2305.10744v1
• Date: Thu, 18 May 2023 06:28:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-19 16:32:20.083755
• Title: Online Resource Allocation in Episodic Markov Decision Processes
• Title（参考訳）: マルコフ決定過程におけるオンライン資源配分
• Authors: Duksang Lee, Dabeen Lee
• Abstract要約: エピソードな有限水平マルコフ決定過程において、オンラインリソース割り当て問題として問題を定式化する。 資源配分のためのオンライン二重ミラー降下アルゴリズムは、真に実現可能な集合を推定する不確実性と誤りを扱う。 我々は、報酬と資源消費関数の下で、オンラインミラー降下アルゴリズムの期待された後悔は、$O(rho-1H3/2SsqrtAT)$、$rhoin(0,1)$が予算パラメータであることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• 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 resource allocation problem in an episodic finite-horizon Markov decision process with unknown non-stationary transitions and stochastic non-stationary reward and resource consumption functions for each episode. We provide an equivalent online linear programming reformulation based on occupancy measures, for which we develop an online mirror descent algorithm. Our online dual mirror descent algorithm for resource allocation deals with uncertainties and errors in estimating the true feasible set, which is of independent interest. We prove that under stochastic reward and resource consumption functions, the expected regret of the online mirror descent algorithm is bounded by $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.
• Abstract（参考訳）: 本稿では,多段階意思決定プロセスを必要とする複数期間にわたる長期資源配分問題について検討する。 未知の非定常遷移と確率的非定常報酬と資源消費関数を有するエピソディック有限ホリゾンマルコフ決定過程において、オンライン資源配分問題として問題を定式化する。 我々は,オンラインミラー降下アルゴリズムを開発するための占有測度に基づく等価なオンラインリニアプログラミング再構成を提供する。 資源割当のためのオンライン二重ミラー降下アルゴリズムは、真の実現可能集合の推定における不確実性と誤りを扱う。 確率的報酬と資源消費関数の下では、オンラインミラー降下アルゴリズムの期待された後悔は$O(\rho^{-1}{H^{3/2}}S\sqrt{AT})$で束縛され、$\rho\in(0,1)$は予算パラメータ、$H$は地平線の長さ、$S$と$A$は状態と行動の数、$T$はエピソード数である。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。