論文の概要: No-Regret Online Reinforcement Learning with Adversarial Losses and
Transitions
- arxiv url: http://arxiv.org/abs/2305.17380v3
- Date: Thu, 26 Oct 2023 17:12:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-28 01:38:02.624974
- Title: No-Regret Online Reinforcement Learning with Adversarial Losses and
Transitions
- Title（参考訳）: 逆損失と遷移を考慮したオンライン強化学習
- Authors: Tiancheng Jin, Junyan Liu, Chlo\'e Rouyer, William Chang, Chen-Yu Wei,
Haipeng Luo
- Abstract要約: 対戦型マルコフ決定プロセスのための既存のオンライン学習アルゴリズムは、T$ラウンドのインタラクションの後、後悔して$O(sqrtT)を達成します。
これは、対向遷移関数が非回帰学習を不可能にすることが示されているためである。
我々は、$widetildeO(sqrtT + CtextsfP)$ regretというアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 39.864174754882754
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Existing online learning algorithms for adversarial Markov Decision Processes
achieve ${O}(\sqrt{T})$ regret after $T$ rounds of interactions even if the
loss functions are chosen arbitrarily by an adversary, with the caveat that the
transition function has to be fixed. This is because it has been shown that
adversarial transition functions make no-regret learning impossible. Despite
such impossibility results, in this work, we develop algorithms that can handle
both adversarial losses and adversarial transitions, with regret increasing
smoothly in the degree of maliciousness of the adversary. More concretely, we
first propose an algorithm that enjoys $\widetilde{{O}}(\sqrt{T} +
C^{\textsf{P}})$ regret where $C^{\textsf{P}}$ measures how adversarial the
transition functions are and can be at most ${O}(T)$. While this algorithm
itself requires knowledge of $C^{\textsf{P}}$, we further develop a black-box
reduction approach that removes this requirement. Moreover, we also show that
further refinements of the algorithm not only maintains the same regret bound,
but also simultaneously adapts to easier environments (where losses are
generated in a certain stochastically constrained manner as in Jin et al.
[2021]) and achieves $\widetilde{{O}}(U + \sqrt{UC^{\textsf{L}}} +
C^{\textsf{P}})$ regret, where $U$ is some standard gap-dependent coefficient
and $C^{\textsf{L}}$ is the amount of corruption on losses.
- Abstract（参考訳）: 既存の対戦型マルコフ決定過程のオンライン学習アルゴリズムは、もし損失関数が敵によって任意に選択されたとしても、その遷移関数が固定されなければならないという注意を払っても、$T$の相互作用の後に${O}(\sqrt{T})$後悔を達成する。
これは、対向遷移関数が非回帰学習を不可能にすることが示されているためである。
このような不合理な結果にもかかわらず、本研究では、敵の悪意の程度で後悔がスムーズに増加し、敵の損失と敵の遷移の両方を処理できるアルゴリズムを開発する。
より具体的には、まず、$\widetilde{O}}(\sqrt{T} + C^{\textsf{P}})$ regret ここで、$C^{\textsf{P}}$は、遷移関数がいかに敵対的であり、少なくとも${O}(T)$であるかを測るアルゴリズムを提案する。
このアルゴリズム自体は$c^{\textsf{p}}$の知識を必要とするが、我々はこの要件を取り除くブラックボックス還元アプローチをさらに開発する。
さらに、アルゴリズムのさらなる改良は、同じ後悔境界を維持するだけでなく、より簡単な環境(Jin et al. [2021] のような確率的に制約された方法で損失が発生する)にも同時に適応し、$\widetilde{O}}(U + \sqrt{UCUCtextsf{L}}} + C^{\textsf{P}})$ regret, ここで$U$は標準的なギャップ依存係数であり、$C^{\textsf{L}}$は損失の破損量であることを示す。
関連論文リスト
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。
既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
論文 参考訳（メタデータ） (2023-10-17T19:43:37Z) - Online Learning in Dynamically Changing Environments [11.731001328350983]
一般的な未知の非定常過程からサンプルを引き出す際に,オンライン学習とオンライン後悔の問題を考察する。
我々は、任意の有限VC-次元クラスに対する予想される最悪のケースに対する厳密な($sqrtlog T$ factorまで)有界な$O(sqrtKTcdotmathsfVC(mathcalH)log T)$を証明する。
我々はこれらの結果を、未知の基準測度を持つ一般的なスムーズな逆過程に拡張する。
論文 参考訳（メタデータ） (2023-01-31T21:10:03Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear
Contextual Bandits and Markov Decision Processes [59.61248760134937]
本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。
提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。
本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
論文 参考訳（メタデータ） (2022-12-12T15:04:56Z) - 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) - The best of both worlds: stochastic and adversarial episodic MDPs with
unknown transition [49.78053380710322]
我々は,エピソードT$でマルコフ決定過程を学習する上で,両世界の最良の問題を考える。
最近の[Jin and Luo, 2020]による研究は、固定遷移が分かっているときにこの目標を達成する。
本研究では,同じFollow-the-Regularized-Leader(textFTRL$)フレームワークを新しいテクニックのセットと組み合わせることで,この問題を解決する。
論文 参考訳（メタデータ） (2021-06-08T05:46:35Z) - Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。
強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文 参考訳（メタデータ） (2021-03-21T11:43:35Z) - Projection-free Distributed Online Learning with Strongly Convex Losses [37.08975118221237]
損失関数の強い凸性を利用して、後悔と通信の複雑さを改善する。
本アルゴリズムは多対数因子に縛られた$o(t2/3log t)$ regretを得るのにほぼ最適である。
論文 参考訳（メタデータ） (2021-03-20T05:38:51Z) - Simultaneously Learning Stochastic and Adversarial Episodic MDPs with
Known Transition [38.28925339231888]
我々は,世界最良保証付きの最初のアルゴリズムを開発した。
損失が逆ならば、$mathcalO(log T)$ regretを達成します。
より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
論文 参考訳（メタデータ） (2020-06-10T01:59:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。