論文の概要: A General Framework for Sequential Decision-Making under Adaptivity
Constraints
- arxiv url: http://arxiv.org/abs/2306.14468v1
- Date: Mon, 26 Jun 2023 07:20:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-27 14:46:54.596236
- Title: A General Framework for Sequential Decision-Making under Adaptivity
Constraints
- Title（参考訳）: 適応性制約下における逐次意思決定の一般的な枠組み
- Authors: Nuoya Xiong, Zhuoran Yang, Zhaoran Wang
- Abstract要約: 適応性制約(まれなポリシースイッチ)とバッチ学習(バッチ学習)という2つの制約の下で、一般的なシーケンシャルな意思決定について検討する。
稀なポリシースイッチの制約に対して、バッチ数で$widetildemathcalO(sqrtK+K/B)$ regretを達成するアルゴリズムを提供する。
バッチ学習制約に対して、バッチ数で$widetildemathcalO(sqrtK+K/B)$ regretを提供するアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 116.64703675631885
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We take the first step in studying general sequential decision-making under
two adaptivity constraints: rare policy switch and batch learning. First, we
provide a general class called the Eluder Condition class, which includes a
wide range of reinforcement learning classes. Then, for the rare policy switch
constraint, we provide a generic algorithm to achieve a
$\widetilde{\mathcal{O}}(\log K) $ switching cost with a
$\widetilde{\mathcal{O}}(\sqrt{K})$ regret on the EC class. For the batch
learning constraint, we provide an algorithm that provides a
$\widetilde{\mathcal{O}}(\sqrt{K}+K/B)$ regret with the number of batches $B.$
This paper is the first work considering rare policy switch and batch learning
under general function classes, which covers nearly all the models studied in
the previous works such as tabular MDP (Bai et al. 2019; Zhang et al. 2020),
linear MDP (Wang et al. 2021; Gao et al. 2021), low eluder dimension MDP (Kong
et al. 2021; Gao et al. 2021), generalized linear function approximation (Qiao
et al. 2023), and also some new classes such as the low $D_\Delta$-type Bellman
eluder dimension problem, linear mixture MDP, kernelized nonlinear regulator
and undercomplete partially observed Markov decision process (POMDP).
- Abstract（参考訳）: 適応性制約(まれなポリシースイッチ)とバッチ学習(バッチ学習)という2つの制約の下で、一般的なシーケンシャルな意思決定を研究するための第一歩を踏み出します。
まず,多種多様な強化学習クラスを含むeluder条件クラスと呼ばれる一般クラスを提供する。
そして、まれなポリシースイッチの制約に対して、EC クラスで $\widetilde{\mathcal{O}}(\log K) $ switch cost を $\widetilde{\mathcal{O}}(\sqrt{K})$ regret で達成するための一般的なアルゴリズムを提供する。
バッチ学習制約に対しては、バッチ数$bで$\widetilde{\mathcal{o}}(\sqrt{k}+k/b)$ regretを提供するアルゴリズムを提供する。
$ This paper is the first work considering rare policy switch and batch learning under general function classes, which covers nearly all the models studied in the previous works such as tabular MDP (Bai et al. 2019; Zhang et al. 2020), linear MDP (Wang et al. 2021; Gao et al. 2021), low eluder dimension MDP (Kong et al. 2021; Gao et al. 2021), generalized linear function approximation (Qiao et al. 2023), and also some new classes such as the low $D_\Delta$-type Bellman eluder dimension problem, linear mixture MDP, kernelized nonlinear regulator and undercomplete partially observed Markov decision process (POMDP).
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - 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) - 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) - A Model Selection Approach for Corruption Robust Reinforcement Learning [33.39130388569606]
我々は,移行と報酬の両面において,敵対的腐敗を伴う強化学習に取り組むためのモデル選択手法を開発した。
我々のアルゴリズムは、$widetildemathcalO(minfrac1Delta, sqrtT+C)$で、$T$はエピソード数、$C$は腐敗の総量、$Delta$はベストとセカンドベストのポリシーの報酬ギャップである。
論文 参考訳（メタデータ） (2021-10-07T15:59:01Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
スイッチングコストの低い線形MDPのための最初のアルゴリズムを提案する。
このアルゴリズムは$widetildeoleft(sqrtd3h4kright)$ regretをほぼ最適の$oleft(d hlog kright)$グローバルスイッチングコストで達成する。
論文 参考訳（メタデータ） (2021-01-02T18:41:27Z) - Learning Infinite-horizon Average-reward MDPs with Linear Function
Approximation [44.374427255708135]
線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。
まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。
次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
論文 参考訳（メタデータ） (2020-07-23T08:23:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。