Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs

Thank you for your supportive feedback. We will answer your question as follows:

Q1: The novelty of this paper may be limited. Most of the analysis follows from that of horizon-free reinforcement learning for linear mixture MDPs with stochastic rewards [1].

A1: We agree that the our analysis framework follows [1]. However, compared to [1] and other very related work [2][3], our paper actually introduces several new techniques. First, compared to [2][3], we use occupancy-measure, rather than policy-optimization, to update the policy, making our work the first to apply occupancy-measure to this setting. Second, compared to [1], we adopted random policy, which inevitably introduce a new policy noise term $\sum_{k=1}^K\sum_{h=1}^H \mathbb{E}\big[Q_{k, h}(s_h^k, a) - Q_{k, h}^{\pi^k}(s_h^k, a)\big] - \big(Q_{k,h}(s_h^k, a_h^k) - Q_{k, h}^{\pi^k}(s_h^k, a_h^k) \big)$ with $a\sim\pi^k_h(\cdot|s_h^k)$. This term is bounded by $\tilde{O}(\sqrt{KH})$ by using Azuma-Hoeffding's inequality and therefore introduces an unwanted dependency on $H$. To tackle this issue, we introduce a notion of conditional variance of $Q_{k, h+1}^{2^m}(s_{h+1}^k, a)$ into the analysis of Algorithm 3 (HOME) to bound the policy noise in a recursive way and settle the poly$(H)$ dependency down. This is also a new technique that does not appear in previous analysis [1]. Third, we also proposed a novel lower bound showing that horizon-free regret can only be achieved under finite state assumption.

Q2: The occupancy measure-based algorithm is not computationally efficient as the running time has polynomial dependence on the state number S and action number A.

A2: We agree with the reviewer as we have discussed in Remark E.2. The necessity of computing all the $\Omega(S)$ entries of occupancy measure is the limitation of our algorithm. However, as we have shown in Section 6, using occupancy measure is the key technique to get rid of the $H$ dependency in online mirror descent regret. We will explore more efficient algorithms in the future work.

References:

[1] Zhou, D., & Gu, Q. (2022). Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint arXiv:2205.11507.

[2] He, J., Zhou, D., & Gu, Q. (2022, May). Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In International Conference on Artificial Intelligence and Statistics (pp. 4259-4280). PMLR.

[3] Cai, Q., Yang, Z., Jin, C., & Wang, Z. (2020, November). Provably efficient exploration in policy optimization. In International Conference on Machine Learning (pp. 1283-1294). PMLR.

Thank you for your positive and constructive feedback. We answer your questions as follows:

Q1:I think it should be clearer that also homogenous transition dynamics are required for obtaining reward free bounds. Therefore, the Bellman optimality equation at page 3 should not have ℎ in the footnote of the operator P.

A1: Thank you for your suggestion and we have fixed it in the reversion.

Q2: The value function $\bar{V}_k,1$ is never formally defined in the paper.

A2: We are sorry for the missing formal definition. We have added an equation to formally define $\bar{V}_k,1$ in the revision.

Q3: The definition of Regret at page 3 is a bit unclear.

A3: Thank you for your suggestion and we have revised it to make it clearer.

Q4: I think that it is unclear that $I_k^h$ defined in Appendix C.2 is decreasing. After inspecting the proofs I think that what the authors need is that for any fixed k $I_k^h$ is decreasing with respect to $h$. Is this correct ?

A4: Yes, we indeed need for any fixed k then $I_k^h$ is decreasing with respect to $h$. We apologize for the confusion and have made it clear in the revision.

Thank you for your supportive feedback. We will answer your questions as follows.

Q1: The paper makes relatively strong assumptions: linear, finite-state MDPs and full-information feedback. The only novel aspect here is the paper tackles adversarial reward functions rather than fixed or stochastic rewards.

A1: We agree with the reviewer that the assumptions we made (linear, full-information) are relatively strong. However, even under these relatively strong but standard assumptions [1][2][3], how to achieve horizon-free regret is still an open problem before our work. Notably, our result is the first horizon-free algorithm in this setting. We agree that finite state space is an extra assumption compared to previous works. However, this is a necessary assumption to achieve a horizon-free regret with adversarial reward, as we have shown in the hardness result in Theorem 5.3.

Q2: To me, the hardness result is more interesting: an unbounded state space will incur regret in $\Omega(\sqrt{H})$. Is this result novel in the literature?

A2: Thank you for your interest! To the best of our knowledge, this result is new and we are the first to show that an infinitely large state space is incompatible with horizon-free regret under adversarial rewards. Therefore, we believe this result is novel and a noteworthy contribution.

Q3: Can the rewards be negative?

A3: Yes, technically, the reward can be negtive. To accommodate this, we can scale up the reward by a factor of 2 and subsequently translate it to the interval $[-1/H, 1/H]$ by subtracting a constant of $1/H$.

Q4: Furthermore, is assumption 3.1 equivalent to the bounded rewards assumption, i.e., if rewards are bounded in [−R,R], we can always scale everything by 1/RH to satisfy assumption 3.1.

A4: Yes, scaling the bounded rewards in [-R, R] by a constant of $1/RH$ can make it satisfy our assumption. We would like to bring to the reviewer's attention that the dependency on $H$ in the regret bound of RL algorithms has two sources: 1) the length of planning horizon, and 2) scale of the rewards. Here to offset the dependency on $H$ contributed by the scale of the reward, we scale down the reward by a factor $H$ so that the total reward in each episode is bounded by one, as suggested by [4].

References:

[1] Zhou, D., & Gu, Q. (2022). Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint arXiv:2205.11507.

[2] Cai, Q., Yang, Z., Jin, C., & Wang, Z. (2020, November). Provably efficient exploration in policy optimization. In International Conference on Machine Learning (pp. 1283-1294). PMLR.

[3] He, J., Zhou, D., & Gu, Q. (2022, May). Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In International Conference on Artificial Intelligence and Statistics (pp. 4259-4280). PMLR.

[4] Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, pp. 3395–3398. PMLR, 2018.

Thank you for your positive feedback. We answer your questions as follows:

Q1: Is it possible to design policy optimization algorithms for this problem setting?

A1: We would like to clarify that policy optimization has previously been applied to adversarial linear mixture MDP [1][2]. However, none of these approaches can guarantee a horizon-free regret upper bound. The reason for this limitation has been shown in Section 6. Specifically, the regret for online mirror descent is $\tilde{O}(H\bar{L}\sqrt{K})$, where $\bar{L}$ is the upper bound of the subgradient. When employing (multiplicative weights update/EXP3 type) policy optimization, due to reward accumulating, the scale of the Q-functions and the correspoding subgradient is $\bar{L}=O(1)$, which will inevitably introduce a dependency on $H$. Therefore, we resort to occupancy measures to tackle this challenge.

Q2: Is it possible to avoid the usage of occupancy measure (which is not quite efficient in real world).

A2: To our knowledge, to tackle adversarial reward, existing approaches are based on either policy optimization or occupancy-measure. As we found that policy optimization is difficult to deduce a horizon-free guarantee, we show that a feasible way is to take occupancy measure-based approach. We will explore other approaches rather than occupancy measure in the future work.

References:

[1] Cai, Q., Yang, Z., Jin, C., & Wang, Z. (2020, November). Provably efficient exploration in policy optimization. In International Conference on Machine Learning (pp. 1283-1294). PMLR.

[2] He, J., Zhou, D., & Gu, Q. (2022, May). Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In International Conference on Artificial Intelligence and Statistics (pp. 4259-4280). PMLR.