Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs

We study episodic linear mixture MDPs with the unknown transition and adversarial rewards under full-information feedback, employing dynamic regret as the performance measure. We start with in-depth analyses of the strengths and limitations of the two most popular methods: occupancy-measure-based and policy-based methods. We observe that while the occupancy-measure-based method is effective in addressing non-stationary environments, it encounters difficulties with the unknown transition. In contrast, the policy-based method can deal with the unknown transition effectively but faces challenges in handling non-stationary environments. Building on this, we propose a novel algorithm that combines the benefits of both methods. Specifically, it employs (i) an occupancy-measure-based global optimization with a two-layer structure to handle non-stationary environments; and (ii) a policy-based variance-aware value-targeted regression to tackle the unknown transition. We bridge these two parts by a novel conversion. Our algorithm enjoys an $\widetilde{\mathcal{O}}(d \sqrt{H^3 K} + \sqrt{HK(H + \bar{P}_K)})$ dynamic regret, where $d$ is the feature dimension, $H$ is the episode length, $K$ is the number of episodes, $\bar{P}_K$ is the non-stationarity measure. We show it is minimax optimal up to logarithmic factors by establishing a matching lower bound. To the best of our knowledge, this is the first work that achieves near-optimal dynamic regret for adversarial linear mixture MDPs with the unknown transition without prior knowledge of the non-stationarity measure.

Paper

Similar papers

Peer review

Reviewer pW8k7/10 · confidence 3/52024-07-09

Summary

This paper studies the adversarial MDPs, which assume unknown (but stochastic) transition models and adversarial rewards. This paper adopts the linear mixture MDP setting, and they aim to study the dynamic regret, where the comparison policy are allowed to be changed along $K$ steps. The algorithm this paper proposed is a combination of policy optimization with exponential weights and online mirror descent. In the meantime, the mirror descent constraint set is updated according to the value target regression framework. This algorithm adopts the merits of both policy optimization and online linear optimization, and achieves optimal rate of regret.

Strengths

This paper is well written. The algorithm, propositions and theorems are presented clearly. From technical side, the algorithm is computationally efficient and very simple. The regret of the algorithm matches the lower bound as well.

Weaknesses

All techniques used in this paper are existed in previous works. Apart from this, I don't see significant drawbacks in this paper.

Questions

I have the following questions for the authors: 1. Does the algorithm apply to other type of non-stationary measures, e.g. switching cost, etc? 2. The lower bound presented in this paper is a constructive lower bound. Can you obtain instance dependent lower bound (given any the transition model, to obtain a lower bound adapts to the transition model)?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes. The authors addressed all the limitations listed in the guidelines.

Reviewer PUu16/10 · confidence 3/52024-07-13

Summary

The paper explores reinforcement learning in linear mixture Markov Decision Processes (MDPs) with adversarial rewards and unknown transitions. It analyzes policy-based and occupancy-measure-based methods, identifying their strengths and weaknesses. The paper introduced an algorithm that merges both approaches to achieve near-optimal dynamic regret, which is the first work that achieves this.

Strengths

1. The paper proposes a novel algorithm that combines the strengths of policy-based and occupancy-measure-based methods 2. According to the authors, the paper achieves near-optimal dynamic regret for adversarial linear mixture MDPs, and is the first work that does this. 3. The paper is presented nicely and compared to previous approaches

Weaknesses

The paper lacks experimental validation, but could be reasonable given it is a theoretical paper. Intuitively it would not scale to complex high dimensional environments empirically if it were implemented into a practical algorithm.

Questions

None.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors discussed limitations of the work.

Reviewer QFuD5/10 · confidence 4/52024-07-15

Summary

This work studies adversarial Linear Mixture MDPs, where the reward function can vary across different episodes, and aims to analyze the dynamic regret, where the baseline policy can also change across different episodes with respect to the dynamic environment. The authors propose a novel algorithm with a theoretical guarantee of the dynamic regret. In addition, the authors provide a hard-to-learn instance, which suggests that the regret guarantee cannot be improved by any algorithm.

Strengths

1. This work provide a algorithm with theoretically guarantee for the dynamic regret with adversarial environment, which is strictly stronger guarantee than the previous static regret analysis. 2. The authors provide a hard-to-learn instance, which suggests that the proposed algorithm has already achieved a near-optimal regret guarantee. 3. This paper is well-written and easy to follow.

Weaknesses

1. The proposed algorithm is computationally inefficient. Firstly, calculating the feature $\phi{k,h}$ requires evaluating the value function over all possible next states. Secondly, the performance of the occupancy-measure-based method relies on solving a global optimization problem over all state-action pairs. For methods with linear function approximation, such state/action spaces are usually huge and require high computational costs in the previous two steps. Though this is a common issue in the analysis of linear mixture MDPs and occupancy-measure-based methods, it will still affect the impact of the proposed algorithm. 2. There is a similar setting that also considers the dynamic regret guarantee (e.g., [1]) in a non-stationary environment. This non-stationary MDP setting measures the environment's dynamics by the difference between adjacent reward/transition functions. In contrast, this work measures the dynamics by the difference between adjacent policy/occupancy. It is better to make a comparison with this setting and previous results. Otherwise, it is challenging to compare fairly with previous work or evaluate the bound of the dynamic regret in this study. [1] Nonstationary Reinforcement Learning with Linear Function Approximation

Questions

1.For the regret guarantee, why does there exist a $\sqrt{HK \cdot H}$ term? It is directly dominated by the first term $d\sqrt{H^3K}$. 2. The baseline policy $\pi_k^c$ should be chosen with knowledge of the online reward function before episode $k$, , or it can depend on the future reward function until the end of episode $K$.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Reviewer xu5Q6/10 · confidence 1/52024-07-15

Summary

Disclaimer: This specific area falls outside my expertise, as indicated by my confidence score. Nevertheless, I have carefully reviewed this paper and the relevant literature to offer the most informed feedback possible. This paper studies the dynamic regret for adversarial linear mixture MDPs, with unknown transitions and full-information feedback. It introduces a hybrid algorithm that combines a policy-based variance-aware value target regression method [Zhou 2021] with the occupancy-measure based method [Li et. al. 2024a]. The authors provide the dynamic regret analysis of this hybrid algorithm, demonstrating its near-optimality up to logarithmic factors by showing both upper and lower bound. In particular, it removes dependence on the state number S from the prior result in Li et. al 2024a.

Strengths

It establishes a near-optimal dynamic regret for the first-time in its setting, improving over the results presented in [Li et al. 2024a],

Weaknesses

1. I feel that the contributions of this paper could be highlighted better, given that the proposed algorithm involves various components from the literature. I’m not sure if I fully understand, but it seems that the main contribution lies more in the regret analysis rather than the algorithm itself. The proposed algorithm seems to be a combination of existing components from prior works [Li et. al 2024a and Zhou et al. 2021]. In particular, would it be fair to describe the proposed algorithm as Algorithm 1 in Li et. al 2024a, leveraging the techniques from UCRL-VTR+ [Zhou et. al 2021] to compute the confidence set, in place of the EstimateTransition routine in Algorithm 4 of Li et. al 2024a? 2. The organization and the clarity of Section 3 can be improved to help with better understanding. Although Section 3.1 and 3.2 seem to aim to outline the pros and cons to motivate the proposed hybrid approach in Section 3.3, a more concise presentation could improve readability. Additionally, reordering 3.2 and 3.1 may better align with the flow in Sec. 3.3. 3. The limitation of the work should explicitly mention the assumptions on access to the oracle in Algorithm 2. It’s a strong assumption and seems crucial in the ability to remove the dependence on the number of states S in the upper bound. Minor: typos noted below Line 243: The formula for KL-divergence Line 326: “Combinin”

Questions

In the weakness section, I noted my interpretation of the proposed algorithm. Could you elaborate if any new techniques are developed in this work? It will help me better understand the contributions of the work. Can you comment on the intuition of why it is possible to remove the dependence on S in the upper bound?

Rating

6

Confidence

1

Soundness

3

Presentation

2

Contribution

2

Limitations

The introduction acknowledges the limitation of lower computational efficiency due to the occupancy measure based component. But I think that the additional assumptions regarding access to the oracle, introduced by algorithm 2, should be explicitly stated as a limitation.

Reviewer PUu12024-08-07

I appreciate the authors' response, which is reasonable. I will keep my score unchanged.

Reviewer xu5Q2024-08-11

Thank you for providing the clarifications. I have increased the score accordingly.

Authorsrebuttal2024-08-12

Thank you!

Thank you for your re-evaluation and the revised score. We are happy to discuss work with you.

Authorsrebuttal2024-08-13

Thanks for the review! Have we properly addressed your concerns?

We sincerely appreciate your constructive feedback and are especially grateful for bringing the paper [1] to our attention. We will revise the paper to cite [1] and incorporate the above discussions in the next version. Given that the author-reviewer discussion period is soon coming to an end, please let us know if our response has properly addressed the concerns. We will be happy to provide clarification if you have any further questions. Thanks! Best, Authors

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC