Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations

Summary

The paper studies online adaptive policy selection for nonlinear time-varying discrete-time dynamical systems. The algorithm named GAPS is proposed and is shown to achieve optimal regret, which closes the regret gap between online convex optimization (OCO) and online policy selection. En route, a general proof framework based on exponentially decaying perturbation property is developed that connects online policy selection with OCO. Numerical experiments are provided to demonstrate GAPS's superior performance over baselines.

Strengths

The paper is well-written. The problem and the results seem significant.

Weaknesses

A slight weakness is that the algorithm needs $\Omega(\log T)$ memory instead of a constant complexity to $T$. I did not spot any major weakness.

Questions

I hope the authors can provide clarification for two questions: 1. Can the authors comment on the necessity of assuming Definition 2.6 and Definition 2.7 for achieving optimal regret? 2. Does the variational intensity or a similar quantity also appear in the analysis of Theorem 3.3 (the convex setting)? What is $V$ in that setting?

Rating

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

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

3 good

Limitations

Limitations are discussed in Section 3 and the conclusion. In addition to the ones mentioned in the paper, the algorithm also needs the knowledge of problem parameters $\rho$ and $\epsilon$ (or $\rho$ and $V$) to set the learning rate and run optimally.

Summary

This paper proposes an algorithm, GAPS, for online adaptive policy selection in time-varying systems. The algorithm is shown to achieve optimal $O(\sqrt{T})$ regret based on the contractive perturbation property of the online policy-induced dynamics. Numerical results are provided to verify the performance of GAPS.

Strengths

1. The paper is well-written and organized. The insights behind the main results are effectively presented. 2. The optimal $O(\sqrt{T})$ regret can be achieved using partial derivatives of the dynamics and costs.

Weaknesses

1. The results require a slow change of the policy parameter sequences and an $\epsilon$-time varying contractive perturbation, which cannot handle sudden changes. 2. There is an additional assumption on the initial state.

Questions

1. Is it possible to relax the projection step in the algorithm? 2. It would be interesting to explore the introduction of switching costs in this problem.

Rating

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

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

3 good

Limitations

Yes

Summary

This paper studies online adaptive policy selection for nonlinear time-varying discrete-time dynamical systems. At time step $t \in\mathcal{T}$, the policy picks a control action $u_t$, and the next state and the incurred cost are given by $x_{t+1}=g_t\left(x_t, u_t\right), c_t:=f_t\left(x_t, u_t\right)$, where $g_t(\cdot, \cdot)$ is a time-varying dynamics function and $f_t(\cdot, \cdot)$ is a time-varying stage cost. The goal is to minimize the total cost $\sum_{t=0}^{T-1} c_t$. The regret definition in (2) is similar to [52]( https://arxiv.org/pdf/1708.00075.pdf). They require two key properties to achieve sub-linear regret in this time varying systems. Definition 2.6 requires that Intuitively, two trajectories starting from different states (in a bounded ball) to converge towards each other if they adopt the same slowly time-varying policy parameter sequence, and definition 2.7 requires that the policy class $\pi_{0:T-1}$ can achieve stability if the policy parameters $\theta_{0:T-1}$ vary slowly. Assumption 2.1 is standard (see [52]( https://arxiv.org/pdf/1708.00075.pdf)) while assumption 2.2 ensures starting state stays within an euclidean ball whenever the dynamics changes. Since the complexity of computing $\nabla F_t$ exactly grows proportionally to $t$, the key difference in their approach is that their algorithm GAPS uses $G_t$ to approximate $\nabla F_t\left(\theta_t\right)$ over a batch size of $B$. This results in solving only one MPC optimization problem. Finally in their main theorem 3.6 they show that a regret of $R^L(T)=O\left((1-\rho)^{-\frac{9}{2}}(1+V)^{\frac{1}{2}} T^{\frac{1}{2}}\right)$ is possible without any convexity assumption on $F_t$, where $V$ is the variation intensity of the time-varying system. Finally they empirically validate their algorithm.

Strengths

1) The paper analyzes Online Gradient Descent (OGD) algorithm for time varying systems. They propose the GAPS algorithm which uses the approximate gradient $G_t$ to estimate surrogate function $F_t$. This is also computationally faster than previous methids. 2) They theoretically analyze their algorithm and provide a regret bound of $R^L(T)=O\left((1-\rho)^{-\frac{9}{2}}(1+V)^{\frac{1}{2}} T^{\frac{1}{2}}\right)$ is possible without any convexity assumption on $F_t$, where $V$ is the variation intensity of the time-varying system. This improves over the previous bounds in this setting by a $log(T)$ factor. 3) They show empirically that their algorithm is competitive.

Weaknesses

1) While assumption 2.1 is standard, I think assumption 2.2 is very strong. The implication of the $R_C>R_S+C\left\|x_0\right\|$ in assumption 2.2 is not clear to me. Moreover $\mathcal{G}$ is the set of all possible dynamics/policy sequences ${g_t, \pi_t\}_{t \in \mathcal{T}}$ the environment/policy class may provide and you assume that if $\{g, \pi\}$ is the dynamics/policy at an intermediate time step of a sequence in $\mathcal{G}$, then the time-invariant sequence $\{g, \pi\} \times T$ is also in $\mathcal{G}$. This seems to be very strong assumption. Where do you use it? Are there other works also that require this assumption or is this specific for the time varying system to provide stability? 2) The key novelty in their method lies in using $G_t$ instead of $F_t$ and substituting the ideal sequence by the actual sequence $\theta_{0: t}$. However, doesn't this approach might introduce additional variance in your estimation of the gradient? How do you control for that? Similarly when you truncate your observation to $B$ timesteps rather than the ideal sequence there must be approximation error creeping into your estimation of $F_t$ through $G_t$. How do you account for that? Also it will be great if you can point out where in the theory you deal with these issues. 3) It is not clear to me how the regret improvement occurs in Theorem 3.3 and Theorem 3.6 that results in a regret of $O(\sqrt{T})$ (and improves by a factor of $\log(T)$. The paper has limited discussions on how this happens, and I would like the authors to discuss/clarify this in more details. It will be also great if the authors specifically point out where in their proof the use the assumption 2.1 and 2.2 ti get the improvement. Also why [52]( https://arxiv.org/pdf/1708.00075.pdf) fails to achieve this bound. 4) It makes sense to me that the quantity $V$ occurs in the time-varying system which is similar to the quantity in [Besbes et al.](https://arxiv.org/pdf/1307.5449.pdf). However, it is defined on $f,g$, and policy $\pi$. Shouldn't this $V$ only depend on the environment dynamics and cost $f,g$? Can you please elaborate on this? Also please point out how it comes up in the proof of Theroem 3.6.

Questions

See weakness section.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited 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

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

1) The writing can be improved. I think you some of the definitions and assumptions can be moved to the section 3. Also the authors need to discuss the results more. It is not clear to me exactly what technical novelty over [52]( https://arxiv.org/pdf/1708.00075.pdf) led to the regret bound of $O(\sqrt{T})$ which does not include the $\log T$ factor. 2) The two examples in the main paper seems to be slightly contrived (and i did not see the appendix). Can the authors give moire real life examples where their approach can be used? 3) See weakness section.

Summary

The paper studies online adaptive policy selection for nonlinear systems. The algorithm proposed by the authors, GAPS, is a gradient-based algorithm that achieves the first optimal regret bound in the convex case, and the first local regret bound in the case when convexity does not hold. The authors provided numerical experiments.

Strengths

The novel approach to the online control problem is interesting and closes the $\log T$ gap between the currently established bounds for online nonstochastic control and OGD. The paper is well-organized.

Weaknesses

1. The experiments do not compare the algorithm proposed by the paper to the existing algorithms in online nonstochastic control. It would be interesting to see the comparison against benchmarks in the online control literature including GPC in Algorithm 1, https://arxiv.org/pdf/2211.09619.pdf. 2. Although the analysis is novel, the algorithm proposed is essentially OGD with approximated gradient. The idea of truncation is also very similar to the gradient-based existing algorithms in online control like GPC. 3. To compute the gradient estimator in GAPS, do we need access to all $\theta_t$'s, requiring storing all $\theta_t$?

Questions

1. Can the authors provide more justifications of Definition 2.7 ($\epsilon$-time-varying stability)? How does this assumption compare with the standard assumptions made in existing literature? 2. One of the main contributions of the paper is that it closes the $\log T$ gap between OCO-M based control algorithms and the OGD regret guarantee. However, there are also OCO-M based algorithm that achieves $O(\sqrt{T})$ bound such as in https://arxiv.org/pdf/2210.09903.pdf. Can the authors compare GAPS to this work?

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.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Not applicable.

Summary

This paper proposes a new algorithm, Gradient-based Adaptive Policy Selection (GAPS), for online adaptive policy selection with time-varying dynamics and costs. For analysis, it proposes a general analytical framework for online policy selection. Under this framework, by restricting the problem and policy class to have the contractive perturbation property it identified, GAPS is shown to approximate an ideal online gradient descent algorithm. This results in better regret bounds compared to existing results. When convexity holds, GAPS is the first to achieve optimal regret in this setting; when convexity doesn’t hold, it gives the first local regret bound for online policy selection. Empirical results on two examples in the main text also illustrate GAPS’s better adaptivity to changing environments compared to baselines.

Strengths

1. The results seem to be significant. First, when assuming convexity, the regret bound of the proposed algorithm improves over existing work and fills a gap in the literature. It is the first to achieve the optimal regret of $O(\sqrt{(T)})$ under the discussed setting while requiring less information about the problem. Second, when the cost function is nonconvex, it gives the first local regret bound for online policy selection. 2. The proposed contractive perturbation property and its corresponding analytical framework are general and subsume an existing class (DAC) as well as some known downstream applications. They may be helpful for future research. 3. The paper is well-written, and the presentation of empirical results is clear, which is convincing.

Weaknesses

Overall, the paper seems strong to me, and I have a minor suggestion: If possible, it would be nice to have the result of online gradient descent (OGD) oracle in the numerical experiments. This may help the reader gain more understanding about GAPS’s performance.

Questions

1. Though the proposed contractive perturbation property includes some existing works as special cases, I wonder how likely or hard it is to find a more general property. Typos 1. In Line 216, it seems that some part is missing after “satisfies”.

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

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

3 good

Limitations

As the paper discussed in the Conclusion and Future Directions section, the major limitation of this work may be that the assumptions on the contractive perturbation property and stability are quite strong. It requires the properties should hold for all policy parameters. But still, this work is quite complete, and relaxing the assumptions can be interesting future directions.

Summary

The paper studies online adaptive policy selection in systems with time-varying costs and dynamics. This paper proposes an algorithm that obtains optimal regret bound in the convex case and a local regret bound in the non-convex setting with four assumptions: (1) the dynamics are contractive starting from a ball near 0 if the policy has small variations across time. (2) the dynamics starting from 0 never goes out of an even smaller ball if the policy has small variations across time. (3) the dynamics will start from a point that would never go out of the ball in assumption (1). (4) smoothness and Lipschitzness for the dynamics, policy function, and cost functions. The algorithm does not require Oracle access to the dynamics.

Strengths

The problems under investigation are interesting.

Weaknesses

It seems that the restriction on the dynamics is quite severe.

Questions

Could you give some examples of dynamics where the assumptions hold? I am giving a low score mainly because I am not very sure that I understand the dynamics of interest. If there are good examples which show that the assumptions are not as severe as vacuous, then I will change my score.

Rating

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

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A

Summary

This paper presents a novel algorithm, Gradient-based Adaptive Policy Selection (GAPS), for online policy selection in time-varying systems. The authors introduce a general analytical framework for online policy selection via online optimization. The paper also provides theoretical guarantees for the performance of the GAPS algorithm under some assumptions on the stability of the dynamical system and on the convexity of the surrogate cost function. Complementary local bounds are also give in the case of nonconvex cost.

Strengths

The paper is well-organized and easy to follow, with clear explanations of the theoretical concepts and practical implementation details. The authors provide detailed proofs of their theoretical results in the appendices, as well as numerical experiments to document the performance of the GAPS algorithm in two concrete example settings. On the math side, while I did not check the details of the proof, I find the underlying perturbative idea new and interesting, and on a high level the steps of the proof check out.

Weaknesses

The main weakness of the paper is, given its novelty, that it is hard for the reader to understand how restrictive the set of assumptions that are put on the dynamical systrem. This holds for both assumptions of Theorem 3.3: Convexity of $F$ and $\epsilon$-time varying contractive perturbation/stability. It is good that the authors give examples of systems where these assumptions hold, and describe in Lemma 2.8 how the time-invariant stability can be translated to these conditions, but I still find it a bit hard to understand how restrictive these conditions are. For instance, I imagine that in the case of a multistable dynamical system the contractive perturbation property would not hold?

Questions

one main question listed in the weaknesses.

Rating

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

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

4 excellent

Contribution

3 good

Limitations

Some of the limitations havebeen listed in the conclusions, but perhaps a more extended discussion about the applicability of the assumptions would be informative.

Response to author's rebuttal

I thank the authors for their response. I have some further questions to understand the paper correctly: - Thank you for clarifying assumption 2.2. - I want to dig deeper into this repeating sequence of $g, \pi$ to satisfy contractive perturbation and stability idea. I understand that real-life problems may not satisfy this and this is only required for proof. However, it is important to know whether this assumption makes the proof trivial or can be removed for future works. Can the authors clarify how this is used in the proof? - Thank you for clarifying the variance of the gradient comment. However, do you have any intuition about how you are controlling the bias? - The writing style of this paper is unsatisfactory. For example, corollary D.4 which actually discusses how we can get the improvement is shifted to the appendix. I think these things should be discussed in the main paper in detail as this paper is more theoretical in nature. I have not checked the proof of corollary D.4 in detail but it is used to prove Theorem D.5 on bounding actual stage cost and Theorem D.6 for bounding the bias. - The buffer length $B$ plays a crucial role in gradient concentration. Can the authors discuss how it is chosen, and how choosing it too small or large affects the proof? - Thank you for your clarification on $V$, and experiments.

Response to rebuttal

I thank the authors for their response. My positive assessment remains unchanged.