論文の概要: Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback
- arxiv url: http://arxiv.org/abs/2310.11550v1
- Date: Tue, 17 Oct 2023 19:43:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-19 18:37:52.738883
- Title: Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback
- Title（参考訳）: バンディットフィードバックを伴う逆線形mdpの最適後悔に向けて
- Authors: Haolin Liu, Chen-Yu Wei, Julian Zimmert
- Abstract要約: 線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。
既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
- 参考スコア（独自算出の注目度）: 30.337826346496385
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online reinforcement learning in linear Markov decision processes
with adversarial losses and bandit feedback, without prior knowledge on
transitions or access to simulators. We introduce two algorithms that achieve
improved regret performance compared to existing approaches. The first
algorithm, although computationally inefficient, ensures a regret of
$\widetilde{\mathcal{O}}\left(\sqrt{K}\right)$, where $K$ is the number of
episodes. This is the first result with the optimal $K$ dependence in the
considered setting. The second algorithm, which is based on the policy
optimization framework, guarantees a regret of
$\widetilde{\mathcal{O}}\left(K^{\frac{3}{4}} \right)$ and is computationally
efficient. Both our results significantly improve over the state-of-the-art: a
computationally inefficient algorithm by Kong et al. [2023] with
$\widetilde{\mathcal{O}}\left(K^{\frac{4}{5}}+poly\left(\frac{1}{\lambda_{\min}}\right)
\right)$ regret, for some problem-dependent constant $\lambda_{\min}$ that can
be arbitrarily close to zero, and a computationally efficient algorithm by
Sherman et al. [2023b] with $\widetilde{\mathcal{O}}\left(K^{\frac{6}{7}}
\right)$ regret.
- Abstract（参考訳）: 我々は,オンライン強化学習を,逆損失や帯域幅フィードバックを伴う線形マルコフ決定過程において,遷移やシミュレータへのアクセスに関する事前知識なく研究する。
従来の手法に比べて後悔性能が向上するアルゴリズムを2つ導入する。
最初のアルゴリズムは計算量的には非効率であるが、$k$がエピソード数であるような$\widetilde{\mathcal{o}}\left(\sqrt{k}\right)$の後悔を保証する。
これは、考慮された設定における最適な$K$依存による最初の結果である。
第2のアルゴリズムは、ポリシー最適化フレームワークに基づいており、$\widetilde{\mathcal{o}}\left(k^{\frac{3}{4}} \right)$の後悔を保証し、計算効率が高い。
両結果は,Kongらによる計算非効率アルゴリズムにより,最先端のアルゴリズムよりも大幅に改善された。
[2023] with $\widetilde{\mathcal{O}}\left(K^{\frac{4}{5}}+poly\left(\frac{1}{\lambda_{\min}}\right) \right)$ regret, for some problem-dependent constant $\lambda_{\min}$, and a computerly efficient algorithm by Sherman et al.
2023b] と $\widetilde{\mathcal{o}}\left(k^{\frac{6}{7}} \right)$ を持つ。
関連論文リスト
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。
注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
論文 参考訳（メタデータ） (2024-06-03T11:53:44Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Nearly Optimal Algorithms with Sublinear Computational Complexity for
Online Kernel Regression [13.510889339096117]
後悔と計算コストのトレードオフは、オンラインカーネル回帰の根本的な問題である。
AOGD-ALDとNONS-ALDの2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-14T07:39:09Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - The First Optimal Algorithm for Smooth and
Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
本稿では,スムーズで強靭なミニマックス最適化問題を再考する。
既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。
我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-11T17:33:07Z) - Improved No-Regret Algorithms for Stochastic Shortest Path with Linear
MDP [31.62899359543925]
線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。
我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。
第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
論文 参考訳（メタデータ） (2021-12-18T06:47:31Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear
Bandits [16.103685478563072]
本稿では,一般制約付き線形帯域について考察する。
目的は、各ラウンドにおける一連の制約の対象となる水平線上の累積報酬を最大化することである。
本稿では,この問題に対する悲観的最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-10T07:30:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。