Summary
This paper studies the theoretical performance of an optimistic variant of PPO in episodic adversarial linear MDPs with full-information feedback (i.e., without assuming the reward functions are linear in the feature map), and establishes a regret bound of O(d^3/4 H^2 K^3/4) that matches the optimal regret bound in both stochastic linear MDPs and adversarial linear MDPs. The authors also introduce a new multi-batched updating mechanism to enable a new covering number argument of value and policy classes in their theoretical analysis.
Strengths
Existing theoretical studies of PPO mainly focus on linear mixture MDPs with full-information feedback, which are implemented in a model-based manner and require an integration of the individual base model. In comparison, this work studies another set of linear MDPs that have low-rank representations and proposes a new optimistic variant of PPO that is provably efficient in both stochastic linear MDPs and adversarial linear MDPs.
In particular, this work exhibits several promising results:
1. From the algorithmic perspective, the proposed algorithm involves the novel design of a multi-batched updating mechanism and a policy evaluation step via average rewards.
2. Regarding the performance guarantee, the authors establish the optimal regret bound of O(d^3/4 H^2 K^3/4) with two fundamental findings. Instead of using the existing covering argument in linear MDPs, this work presents a new covering number argument for the value and policy classes. In addition, to ensure the sublinear regret, careful analysis has been done to analyze the drift between adjacent policies to control the error arising from the policy evaluation step.
3. Apart from the regret guarantee, it also provides a PAC guarantee as sample complexity, which allows fair comparison with existing works in this line.
This work is well-organized and clearly articulates each part with the corresponding motivation, challenges, as well as technical novelties in its solutions. Overall, this paper is technically sound and demonstrates considerable technical novelties. It provides a better understanding of PPO in a class of MDPs with function approximation, which potentially benefits policy optimization in practice.
Weaknesses
While this paper provides insights into the PPO algorithm in linear MDPs, it does have several drawbacks:
1. One of the claimed novelties is the multi-batched updating mechanism, which coincides with the similar idea of "policy switch" in literature. However, there is no discussion of the existing works that involve "policy switch", and thus it is not clear whether the computational efficiency is solely brought by the policy switch scheme.
2. Right now, the regret bound requires the batch size to be O(\sqrt{d^3 K}), with leads to the number of batches being O(\sqrt{K}). But whether this choice of batch size and the number of batches is optimal remains to be unknown. It would be worthwhile to study and discuss the balance between the batch size and the number of batches, the optimal choice, how the balance will affect the regret.
3. Right now, this is solely theory-based work. As PPO is applied widely in practice, it will be beneficial to include simple benchmark empirical studies to demonstrate its effectiveness.
Questions
1. In the introduction, the authors mentioned both Cai et al. and He et al. that study linear mixture MDPs are implemented in a model-based manner, whereas existing theoretical studies in linear MDPs are typically value-based methods. However, from the algorithmic perspective, algorithms in Cai et al. and He et al. also perform regularized least-square approximation on value functions in the policy evaluation step. Do you treat all algorithmics that tries to explicitly learn /approximate the transition model (i.e., \hat{p}) as model-based methods in MDPs with function approximation? Could you explain whether your approach falls into the model-based category? If not, which step makes the difference? Is the multi-batched update the main reason that makes the proposed algorithm more computationally efficient compared to the direct extension of the existing OPPO method to linear MDPs from the algorithmic perspective?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
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.
Limitations
This is a theory paper with no potential negative social impact under the discussed context.