Fugu-MT 論文翻訳(概要): Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds

論文の概要: Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds

arxiv url: http://arxiv.org/abs/2306.06836v3
Date: Thu, 7 Mar 2024 15:29:58 GMT
ステータス: 処理完了
システム内更新日: 2024-03-08 18:17:38.266447
Title: Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds
Title（参考訳）: 関数近似を用いた強化学習における重機付きリワードの処理:ミニマックス最適およびインスタンス依存レグレト境界
Authors: Jiayi Huang, Han Zhong, Liwei Wang, Lin F. Yang
Abstract要約: 本研究では,線形関数近似を用いた強化学習におけるそのような報奨の課題に対処する。我々はまず,重み付き線形包帯に対するtextscHeavy-OFUL というアルゴリズムを設計し,インセンス依存の$T$-round regret of $tildeObig を実現した。我々の結果は、オンライン回帰問題全般において、重くノイズを扱うことに独立した関心を持つような、新しい自己正規化集中不等式によって達成される。
参考スコア（独自算出の注目度）: 26.277745106128197
License: http://creativecommons.org/licenses/by/4.0/
Abstract: While numerous works have focused on devising efficient algorithms for reinforcement learning (RL) with uniformly bounded rewards, it remains an open question whether sample or time-efficient algorithms for RL with large state-action space exist when the rewards are \emph{heavy-tailed}, i.e., with only finite $(1+\epsilon)$-th moments for some $\epsilon\in(0,1]$. In this work, we address the challenge of such rewards in RL with linear function approximation. We first design an algorithm, \textsc{Heavy-OFUL}, for heavy-tailed linear bandits, achieving an \emph{instance-dependent} $T$-round regret of $\tilde{O}\big(d T^{\frac{1-\epsilon}{2(1+\epsilon)}} \sqrt{\sum_{t=1}^T \nu_t^2} + d T^{\frac{1-\epsilon}{2(1+\epsilon)}}\big)$, the \emph{first} of this kind. Here, $d$ is the feature dimension, and $\nu_t^{1+\epsilon}$ is the $(1+\epsilon)$-th central moment of the reward at the $t$-th round. We further show the above bound is minimax optimal when applied to the worst-case instances in stochastic and deterministic linear bandits. We then extend this algorithm to the RL settings with linear function approximation. Our algorithm, termed as \textsc{Heavy-LSVI-UCB}, achieves the \emph{first} computationally efficient \emph{instance-dependent} $K$-episode regret of $\tilde{O}(d \sqrt{H \mathcal{U}^*} K^\frac{1}{1+\epsilon} + d \sqrt{H \mathcal{V}^* K})$. Here, $H$ is length of the episode, and $\mathcal{U}^*, \mathcal{V}^*$ are instance-dependent quantities scaling with the central moment of reward and value functions, respectively. We also provide a matching minimax lower bound $\Omega(d H K^{\frac{1}{1+\epsilon}} + d \sqrt{H^3 K})$ to demonstrate the optimality of our algorithm in the worst case. Our result is achieved via a novel robust self-normalized concentration inequality that may be of independent interest in handling heavy-tailed noise in general online regression problems.
Abstract（参考訳）: 多くの研究は、一様有界の報酬を持つ強化学習(rl)のための効率的なアルゴリズムを考案することに焦点をあてているが、いくつかの$\epsilon\in(0,1]$ に対して有限$(1+\epsilon)$-th moments の報酬が \emph{heavy-tailed} である場合、大きな状態作用空間を持つrlのサンプルまたは時間効率のよいアルゴリズムが存在するかどうかという疑問が残されている。本稿では、線形関数近似を用いたRLにおけるそのような報酬の課題に対処する。まず,重尾付き線形バンドイットのアルゴリズムである \textsc{heavy-oful} を設計し,$\tilde{o}\big(d t^{\frac{1-\epsilon}{2(1+\epsilon)}} \sqrt{\sum_{t=1}^t \nu_t^2} + d t^{\frac{1-\epsilon}{2(1+\epsilon)}}\big)$,この種の \emph{first} を達成する。ここで、$d$は特徴次元であり、$\nu_t^{1+\epsilon}$は$(1+\epsilon)$-th central moment of the reward at the $t$-th roundである。さらに, 確率的および決定論的線形バンドイットの最悪の場合に適用した場合, 上記の境界はミニマックス最適であることを示した。次に、このアルゴリズムを線形関数近似を用いてRL設定に拡張する。このアルゴリズムは \textsc{heavy-lsvi-ucb} と呼ばれ、計算効率のよい \emph{instance-dependent} $k$-episode regret of $\tilde{o}(d \sqrt{h \mathcal{u}^*} k^\frac{1}{1+\epsilon} + d \sqrt{h \mathcal{v}^* k})$ を達成する。ここで、$H$はエピソードの長さであり、$\mathcal{U}^* と \mathcal{V}^*$ はそれぞれ、報酬と値関数の中心モーメントを持つインスタンス依存の量スケーリングである。また、マッチングされたミニマックス下界 $\Omega(d H K^{\frac{1}{1+\epsilon}} + d \sqrt{H^3K})$ を提供し、最悪の場合、アルゴリズムの最適性を示す。我々の結果は、オンライン回帰問題全般において重み付きノイズを扱うことに独立した関心を持つような、新しい堅牢な自己正規化集中不等式によって達成される。

論文の概要: Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds

関連論文リスト