論文の概要: Reinforcement Learning and Regret Bounds for Admission Control
- arxiv url: http://arxiv.org/abs/2406.04766v1
- Date: Fri, 7 Jun 2024 09:09:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-10 14:50:13.608254
- Title: Reinforcement Learning and Regret Bounds for Admission Control
- Title（参考訳）: アドミッション制御のための強化学習とレギュレット境界
- Authors: Lucas Weber, Ana Bušić, Jiamin Zhu,
- Abstract要約: 強化学習アルゴリズムの期待された後悔は、未計算の戻り値に対して$Omegaleft(sqrtDXATright)$で制限される。
UCRL2にインスパイアされたアルゴリズムを提案し、その問題の構造を用いて、有限サーバの場合、$O(Slog T + sqrtmT log T)$で期待される全後悔を上位に制限する。
- 参考スコア（独自算出の注目度）: 0.08192907805418585
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The expected regret of any reinforcement learning algorithm is lower bounded by $\Omega\left(\sqrt{DXAT}\right)$ for undiscounted returns, where $D$ is the diameter of the Markov decision process, $X$ the size of the state space, $A$ the size of the action space and $T$ the number of time steps. However, this lower bound is general. A smaller regret can be obtained by taking into account some specific knowledge of the problem structure. In this article, we consider an admission control problem to an $M/M/c/S$ queue with $m$ job classes and class-dependent rewards and holding costs. Queuing systems often have a diameter that is exponential in the buffer size $S$, making the previous lower bound prohibitive for any practical use. We propose an algorithm inspired by UCRL2, and use the structure of the problem to upper bound the expected total regret by $O(S\log T + \sqrt{mT \log T})$ in the finite server case. In the infinite server case, we prove that the dependence of the regret on $S$ disappears.
- Abstract（参考訳）: 強化学習アルゴリズムの期待された後悔は、未公表の戻り値に対して$\Omega\left(\sqrt{DXAT}\right)$で下げられ、そこでは$D$はマルコフ決定プロセスの直径、$X$は状態空間のサイズ、$A$はアクション空間のサイズ、$T$は時間ステップの数である。
しかし、この下界は一般である。
より小さな後悔は、問題構造に関する特定の知識を考慮して得られる。
本稿では、M/M/c/S$キューに$m$のジョブクラスとクラス依存の報酬と保持コストを備えた入場制御問題を考察する。
キューシステムはしばしばバッファサイズが$S$で指数関数的な直径を持つので、以前の下限境界は実用上は禁じられる。
UCRL2にインスパイアされたアルゴリズムを提案し、その問題の構造を用いて、有限サーバの場合、$O(S\log T + \sqrt{mT \log T})$で予想される全後悔を上限にしている。
無限サーバーの場合、遺書の$S$への依存が消えることを証明する。
関連論文リスト
- Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - On learning Whittle index policy for restless bandits with scalable
regret [1.0152838128195465]
強化学習は、優れたリソース割り当てとスケジューリングポリシーを学ぶための魅力的なアプローチである。
ほとんどのRLアルゴリズムの累積後悔は$tilde O(mathsfS sqrtmathsfA T)$、$mathsfS$は状態空間のサイズである。
本稿では,このような問題に対するモデルベースRLアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-07T19:07:02Z) - Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
論文 参考訳（メタデータ） (2021-09-29T14:07:21Z) - 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) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳（メタデータ） (2020-02-23T09:10:14Z) - Logistic Regression Regret: What's the Catch? [3.7311680121118345]
パラメータに対する$L_infty$制約の下で、対数的後悔を伴う下界を導出する。
L$の制約については、十分に大きな$d$の場合、後悔は$d$で線形であるが、$T$で対数化されなくなることが示されている。
論文 参考訳（メタデータ） (2020-02-07T18:36:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。