Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds

Summary

main contributions include two-folds. For heavy-tailed payoffs, design heavy-tailed linear bandits, derive the variance-dependent T-round regret; In terms of Linear MDPs, instance-dependent K-episode regret is acquired. All paper results substantially depend on Huber loss regression techniques.

Strengths

For heavy-tailed linear bandits, the author proposed how to tune the robustification parameter that balances bias and robustness on the fly. for linear MDPs with bounded rewards problem, the author employs separate estimation techniques to handle heavy-tailed rewards and transition kernels, i.e, utilizing adaptive Huber regression to estimate heavy-tailed rewards and weighted ridge regression to estimate the expected next-state value functions.

Weaknesses

The derived regrets depend on the feature dimension, the number of rounds, the variance or central moment of the reward at the t-th round. simultaneously. It seems to have worsened the obtained results comparing to the previous research works. the overall regret scales with feature dimension, again restricting this proposed approach to small dimension problem.

Questions

Since the author believes that their proposed algorithm is computationally effective, why not provide specific examples to demonstrate the practical application effect of the proposed algorithm?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

the authors adequately addressed the limitations.

Summary

In this paper, reinforcement learning problem is considered in the episodic setting for linear bandits and linear MDPs under heavy-tailed rewards with potentially infinite variance. Based on adaptive Huber regression and optimism in the face of uncertainty principle, the authors propose algorithms that utilize conditional reward variance.

Strengths

The paper looks technically sound, and the presentation of the material seems to be good with clearly stated assumptions and theorem statements. On the technical side, the use of adaptive Huber regression in linear bandit and linear MDP setting to tackle heavy-tailed reward distributions is an interesting idea.

Weaknesses

In Assumption 2.6, the centralized moments of order $1+\epsilon$ of the random rewards at each step are assumed to be realizable for each state-action pair, which looks highly unrealistic. Also, in addition to the regret bounds, it would be interesting to see empirical evaluations of the proposed algorithms.

Questions

a) What happens in the absence of the realizability assumption in Assumption 2.6? b) The paper [25] seems to be considering heavy-tailed rewards also, but with finite variance. As such, it would be fair to update the last column of Table 1 and 2 based on finiteness of the variance.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

No substantial discussion on the limitations.

Summary

This paper first addresses Reinforcement learning (RL) with function approximation in the presence of heavy-tailed noises whose central moment is known. In general, these online learning problems rely on the self-normalized inequality to construct a confidence set of optimal parameter . However, the existing self-normalized inequalities have a magnitude of noise term that is intractable with heavy-tailed noises. The authors solve this problem by utilizing adaptive Huber regression and deriving a robust selfnormalized inequality without the noise magnitude term. By using the proposed selfnormalized inequality, they introduce two algorithms. The first algorithm, HEAVY-OFUL, is designed for linear bandits and shown to be minimax optimal. Building upon HEAVYOFUL, they presents HEAVY-LSI-UCB for linear MDPs, which has a better first-order regret bound than previous works. Furthermore, they provide the minimax lower regret bound in linear MDPs with heavy-tailed noises, which implies the minimax optimality of HEAVY-LSI-UCB in the worst case.

Strengths

This paper is the first attempt to deal with heavy-tailed RL with function approximation. - (Optimality) The regret bound of HEAVY-OFUL, is minimax optimal in both stochastic and deterministic linear bandits with heavy-tailed rewards. In addition, the regret bound of HEAVY-LSVI-UCB, recovers the previous variance-aware regret in [1] and improves the existing instance-dependent regrets in linear MDPs [1, 2]. - (Originality) To address the heavy-tailed rewards, the novel robust self-normalized inequality is established.

Weaknesses

- (Computational costs) The first concern is the practical usage of the proposed algorithms. As the authors noted, the regret analyses of the algorithms inherently depend on the robust self-normalized inequality (Theorem 3.3), which bounds the deviation of estimated parameter and the optimal parameter . However, I believe the fact that is obtained from adaptive Huber regression is problematic since it requires iterative optimization steps due to the absence of a closed form for (Line 5 of Alg. 1). Indeed, the proposed algorithms (Alg. 2, 3) contain the additional iterative algorithm (Alg. 1) to ensure their theoretical results, and thus share the intrinsic drawback of Huber regression, which is the linear computational complexity per iteration. In particular, HEAVY-LSVI-UCB utilizes the adaptive Huber regression in order to optimize both rewards and central moments. - (Absent experiments) There are no experiments supporting the theoretical results of the proposed algorithms and addressing concerns about computational costs, even in simple synthetic problems. - (Assumption) The authors assumed that the central moment of rewards is known.

Questions

- Since the paper emphasizes the computational contributions of the proposed algorithms comparing with the existing ones, I think empirical results are needed. Can you provide experiments related to this? - If possible, please discuss computational aspects of the proposed algorithms. - In my understanding, the essential key in handling heavy-tailed noises is the robust self-normalized inequality (Theorem 3.3). However, it seems that the inequality involves the term, $b$, that requires prior information about central moment. While the closet work [1] suppose similar assumption, I think this is a strong condition. Can this be relaxed? - In line 219, the authors claim when $\epsilon=1$ and $\nu=0$, $\forall t$, the regret upper bound of HEAVY-OFUL matches the lower bound of K-armed contextual bandit $\Omega(d)$ [3]. Can you reconsider this argument? To my knowledge, the regret bound proposed in [3] is $\Omega(\sqrt{dT})$, not $\Omega(d)$. Moreover, the settings are different each other in that [3] addresses finite-armed bandits, while this work deals with (possibly) infinite-armed bandits. [1]. Xiang Li and Qiang Sun. Variance-aware robust reinforcement learning with linear function approximation with heavy-tailed rewards. arXiv preprint arXiv:2303.05606, 2023 [2]. Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pages 22384–22429. PMLR, 2022. [3]. Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208–214. JMLR Workshop and Conference Proceedings, 2011.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

There are no limitations discussed in the manuscript.

Summary

The paper considers the problem of linear bandits and linear MDPs, when the noise may be heavy tailed. The main technical tool that they use is the Huber regressor, that enables them to detect extremal noise points that are less informative, and be more robust to these. They show how this regressor can be incorporated into optimistic algorithms to provide sublinear regret bounds.

Strengths

Quality: Claims are sound, and arguments appear to check out. The paper is well-contextualized in the literature. Significance: Problem is relevant to practitioners, and theoretical tools may be reapplied in similar online problems elsewhere as well. Originality: The technical work required to incorporate the huber regressor into the optimistic algorithms is nontrivial, and the efforts are appreciated.

Weaknesses

Clarity: While the writing is well-organized, it is quite dense at times and a slog to parse through: for instances, Sections 2.2 and Section 5. It would be useful to move some things into the appendix and instead of encapsulating commentary into remark environments, including them in the main text to introduce more flow that would make it easier for the reader.

Questions

1. The setup being considered here with heavy-tailed additive noise is different than the situation where the rewards themselves are heavy-tailed. In the current case, the problem is more one of outlier detection to be robust to these extremal noise events. But in the other case, if an arm has a heavy tailed reward, it may be desirable to pull because there is the potential for receiving very high reward from this arm relative to other arms (i.e if an arm like a lottery ticket with low rewards with high probability but immense rewards with small probability). I am concerned that conflating these two problems may lead to confusion. Could the authors comment on this distinction? And if the authors agree, I would appreciate if the title were changed to accurately describe the setup and the distinction were made clear in the text. 2. Could you comment on whether a different definition of heavy-tailed in terms of tail probabilities

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

Yes

Experimental Results

We conducted empirical evaluations of the proposed algorithm for heterogeneous heavy-tailed linear bandits problems, Heavy-OFUL, which can be regarded as a special case of linear MDPs. Comparisons are made between MENU and TOFU, which give the worst-case optimal regret bound in such settings (See Table 1 in our paper). To the best of our knowledge, we are the first to address the challenge of heavy-tailed rewards in RL with function approximation, where $\epsilon$ can be less than 1. Therefore, there are no other algorithms in RL literature that can be compared to us (See Table 2). Results demonstrate the effectiveness of the proposed algorithm, which further corroborates our theoretical regret bounds. Since we couldn't upload images of the experiments to OpenReview for the time being, we show the results of our experiment in the table below. And we will find a way to upload images anonymously as soon as possible. | Algorithms \ Iteration | 1000 | 2000 | 3000 | 4000 | 5000 | 6000 | 7000 | 8000 | 9000 | 10000 | | ---------------------- | ------ | ------ | ------ | ------ | ------ | ------- | ------- | ------- | ------- | ------- | | MENU | 160.00 | 332.78 | 513.98 | 692.20 | 860.32 | 1047.81 | 1219.89 | 1401.82 | 1578.78 | 1673.34 | | TOFU | 179.21 | 362.29 | 544.20 | 728.04 | 910.21 | 1092.74 | 1277.66 | 1460.74 | 1642.73 | 1825.40 | | Heavy-OFUL | 72.96 | 147.50 | 241.67 | 336.48 | 434.02 | 535.09 | 636.30 | 740.47 | 839.75 | 935.39 | Comparison of our algorithm (Heavy-OFUL) versus MENU and TOFU in heavy-tailed linear bandits problems (See Definition 2.1) for $1\times10^4$ rounds. We generate 5 independent paths for each algorithm and show the average cumulative regret. The experimental setup is as follows: Let the feature dimension $d = 10$. For the chosen arm $\phi_t \in \mathcal{D}_t$, reward is $R_t = \langle \phi_t, \theta^* \rangle + \varepsilon_t$, where $\theta^* = \mathbf{1}_d / \sqrt{d} \in \mathbb{R}^d$ so that $\|\theta^*\|_2 = 1$. $\varepsilon_t$ is first sampled from a Student's $t$-distribution with degree of freedom $\text{df}=2$, then is multiplied by a scaling factor $\alpha$ such that the central moments of $\varepsilon_t$ in each rounds are different, where $\log(\alpha) \sim \mathrm{Unif}(0,2)$. Note the variance of $\varepsilon_t$ does not exist and we choose $\epsilon=0.99$. Normalization is made to ensure $L=B=1$.