Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions
Authors: Tongxin Li
Yiheng Lin
Shaolei Ren
Adam Wierman
Venue: NeurIPS 2023 poster (2023)
Keywords: Time-varying MDP
Learning-augmented online algorithm
consistency and robustness tradeoff
TL;DR: We study if Q-value advice from an untrusted machine-learned policy provides more benefits for the consistency and robustness tradeoff than the black-box advice in the context of learning-augmented online algorithms for MDPs.

Abstract: We study the tradeoff between consistency and robustness in the context of a single-trajectory time-varying Markov Decision Process (MDP) with untrusted machine-learned advice. Our work departs from the typical approach of treating advice as coming from black-box sources by instead considering a setting where additional information about  how the advice is generated is available. We prove a first-of-its-kind consistency and robustness tradeoff given Q-value advice under a general MDP model that includes both continuous and discrete state/action spaces. Our results highlight that utilizing Q-value advice enables dynamic pursuit of the better of machine-learned advice and a robust baseline, thus result in near-optimal performance guarantees, which provably improves what can be obtained solely with black-box advice.

Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions
Tongxin Li School of Data Science CUHK-SZ, China
Yiheng Lin Computing Mathematical Sciences Caltech, USA y Sihengl@ealtechh edu
1 litongxin@cuhk. edu.
Shaolei Ren
Adam Wierman Computing + Mathematical Sciences Caltech, USA adams@caltech, edu
Electrical & Computer Engineering
UC Riverside, USA shaolei@ucr. edu
Abstract
We study the tradeoff between consistency and robustness in the context of a single-trajectryy time-varying Markov Decision Process (MDP) with untrusted machine-learned advice. Our work departs from the typical approach of treating advice coming from black-box sources by instead considering setting where additional information about how the advice is generated is available. We prove a trrst-of-its-kine consistency and robustness tradeoff given Q-value advice under a general MDP model that includes both continuous and discrete state/action spaces. Our results highlight that utilizing Q-value advice enables dynamic pursuit of the better of machine-learned advice and a robust baseline, thus result in near-optimal performance guarantees, which provably improves what can be obtained solely with black-box advice.
Introduction
Machine-learned predictions and hand-crafted algorithmic advice are both crucial online decision- making problems, driving a growing interest in learning-augmenti
algorithms [1 that exploit the benefits of predictions to improve the performance for typical problem instances while bounding the worst-case performance 4 To this point, the study of
algorithms has primarily viewed machine-learned advice as potentially untrusted information generated by black-box models. Yet, in many real-world problems, additional knowledge of the machine learning models used to produce ad advice/predictions is often available and can potentially improve the performance of saaming-augmented algorithms.
notable example that motivates our work is the problem minimizing costs (or maximizing rewards) in single-trajectory Markov Decision Process (MDP). More concretely, value- based machine-learner policy गे can be queried to provide suggested actions as advice to the agent at each step 7 Typically, the suggested actions chosen minimize (or maximize, in case of rewards) estimated cost-to-go functions (known as Q-value predictions) based on the current state.
Naturally, in addition to suggested actions, the value function itself can also provide additional information (c.g., the long-term impact of choosing a certain action) potentially useful to the design of caaminggauggment algorithms in MDPs: black-box algorithms and grey-box algorithms. A leaming-augmented algorithm using मे is Mox if गे provides only the suggested action ū to the -aument- algorithm,
algorithm. Thus, this leads to two different designs for Maarinng-uugment
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

whereas it is value-based (a.k.a., grey-box) if provides an estimate of the Q-value function Q (that also implicitly includes a suggested action ū obtained by minimizing Q) to the learning augmented algorithm.
Value-based policies ग often perform well empirically in stationary environments in practice 5 6 However, they may not have performance guarantees in all environments and can perform poorly at times due to a variety of factors, such as non-stationary environments С- policy collapse [12. sample inefficiency [3]. and/or when training data is biased 14. As a consequence, such policies often are referred as "untrusted advice" in the literature on
algorithms, where the notion of "untrusted" highlights the lack of performance guarantees. In contrast, recent studies in competitive online control [5 have begun to focus on worst-case analysis and provide control policies т with strong performance guarantees even in adversarial settings, referred to as robustness, i... т provides "trusted advice." " Typically, the goal of leaniing-augmentn is to perform nearly as well as the untrusted advice when the machine learned policy performs well, a.k.a. achieve consistency, while also ensuring worst-case robustness. Combining the advice of an untrusted machine-learnes policy स and robust policy गे naturally leads to tradeoff between consistency and robustness. In this paper, we explore this tradeoff in a time-varying MDP setting and seek to answer the following key question for learning- augmented online algorithms:
online algorithm [
Can Q-value advice from an untrusted machine-leane learned policy, in a grey-box scenario provide more benefits than the black-box action advice generated by т. in the context of consistency and robustness tradeoffs for MDPs?
1.1 Contributions
We answer the question above in the affirmative by presenting and analyzing a unified projection- based aaurenng-uggented online algorithm (PROjection Pursuit policy, simplified as PROP in Algorithm IT that combines action feedback from a trusted, robust policy मे with an untrusted ML policy R. In addition to offering a consistency and robustness tradeoff for MDPs with black-box advice, our work moves beyond the black-box setting. Importantly, by considering the grey-box setting, the design of PROP demonstrates that the structural information of the untrusted machine- learned advice be leveraged to determine the trust parameters dynamically, which would otherwise be challenging (if not impossible) in a black-box setting. To our best knowledge, PROP is the first-of- algorithm that applies to general MDP models, which allow continuous
its-kin its- or discrete state and action spaces.
Our main results characterize the tradeoff between consistency and robustness for both black-box and grey-box settings in terms of the ratio of expectations, RoE, built upon the traditional consistency and robustness metrics in B 2
2 4 for the competitive ratio. We show in Theorem 5.2 that for the black-box setting, PROP is (1 + O((1 - -))y)) (yy)))-conistent) and (ROB + ((Ar)))rrobus where Moreover, for the black-box setting. PROP cannot be both for any 0 < X < 1 where ry is the diameter of the action space. In sharp contrast, by using a careful design of robustness budget parameter in PROP with Q-value advice (grey-box setting), PROP is 1-consistent and (ROB + o(1) -robustt
0 S x < 1 is a Syper-parameter (1 + -consssecnt and (ROB + o((1 {)))))-rbbur
Our result highlights the benefits of exploiting the additional information informed by the estimated Q-value functions, showing that the ratio of expectations can approach the better of the two policies and ने for any single-trajectory time-varying, and even possibly adversarial environments - if the value-based policy से is optimop then the worst-case RoE(PROP) can approach 1 as governed by consistency parameter; otherwise, RoE(PROP) can be bounded by the ratio of expectations of के subject to an additive term (1) that decreases when the time horizon T increases.
A key technical contribution of our work is to provide the first quantitative characterization of the consistency and robustness tradeoff for model, under both standard block-box and novel grey-box settings. Importantly, PROP is able to leverage a broad class of robust policies, called Wasserstein robust policies, which generalize the well-known contraction principles that are satisfied by various robust policies [24] and have been used to derive regrets for online control [19 25 A few concrete examples of Wasserstein robust
augmente algorithm (PROP) in general MDP
policies applicable for PROP are provided in Table I Section

---

1.2 Related Work
Cearning-Augmente Algorithms with Black-Box Advice. The concept of integrating black-box machine-learned guidance into online algorithms was initially introduced by [26]. 3 coined terms "robustness" and "ccnsistency"" with formal mathematical definitions based on the competitive ratio.
Over the past few years, the consistency and robustness approach has gained widespread popularity and has been utilized to design online algorithms with black-box advice for various applications,
including ski rental 3 22 [X], caching |2722)) bipartite matching 30], online covering B31 (2)
enhanceed algorithms have mainly focused creating meta-strategies that combine online algorithms with black-box -ox predictions, and typically require manual setting of a trust paramm-t to balance consistency and robustness. A more recent learning -ugmented algorithm in [K] investigated the balance between competitiveness and stability in nonlinear control in a black-box box setting. However, this work limits the robust policy to linear quadratic regulator and does not provide a theoretical basis for the selection of the trust parameters. [4 considering distributional advice.
convex body chasing [4, nonlinear quadratic control BJ. The prior studies on
generalized the black-box advice setting by
Online Control and Optimization with Structural Information. Despite the lack of a systematic analysis, recent studies have explored the usage of structural information in online control and optimization problems. Closest to our work, (7] considered a related setting where the Q-value function is available advice, and shows that such information can be utilized to reduce regret in tabular MDP model. In contrast, our analysis applies to more general models that allow continuous state/action spaces. In [17], the dynamical model and the predictions of disturbances in linear control system are shown to be useful in achieving a near-optimal consistency and robustness tradeoff. special realization of grey-box advice, where an approximated cost-to-go function is constructed from structural information that includes the (predicted) dynamical model, costs, and disturbances.
The predictive optimization problem solved by MPC (35 36
16
3
can be regarded
MDP with External Feedback. Feedback from external sources such as control baselines visual explanations 40). and human experts 414 is often available in MDP. This external feedback can be beneficial for various purposes, such as ensuring safety 44 reducing variance [38] training
BR
39
human-like chatbots AI,, and enhancing overall trustworthiness
45 among others. The of
control priors has been proposed by (38] as a way to guarantee the Lyapunov stability of the training process in reinforcement learning. They used the Cemporal-Differeene that combines a RL policy and a control prior, but without providing a theoretical foundation. Another related area is transfer learning in RL, where external Q-value advice from previous tasks can be adapted and utilized in new tasks. Previous research has shown that this approach can outperform an agnostic initialization of Q, but these results are solely based on empirical observations and lack theoretical support 46 4
method to tune coefficient
2 Problem Setting
We consider a state space X' is a subset of a normed vector space embedded with a norm -lx... The actions are chosen from convex and compact set U/ in normed vector space characterized by some norm || llu- Notably, // can represent either continuous actions or the probability distributions used when choosing actions from a finite set The diameter of the action space U/ is denoted by 7 max ||u]lee- - Px be the transition probability, where Px is a set of probability measures on X. We consider time-varying costs G. : X x - R,, while rewards can be treated similarly by adding a negative sign. An initial state To E X' is fixed. This MDP model is compactly represented by MDP(X', UU, P.c).
single-trajectory, time-varying MDP with T discrete time steps. The
Denote [T] == (O.....
1). For each time step E [T], let P : X
The goal of a policy in this MDP setting to minimize the total cost over all T steps. The policy agent has no access to the full MDP. At each time step E [T]. only the incurred cost value et (Ø, u,) and the next state xz+1 P. (- (I, Ue) are revealed to the agent after playing an action u E U. We denote policy by = (T++ t E [T]) where each n. X + l chooses an action u, when observing
'The action space 1/ is assumed to be a continuous, convex, and compact set for more generality. When the actions are discrete, 24 can be defined as the set of all probability distributions on finite action space. We relegate the detailed discussions in Appendix A.2 and
3

---

It at step t E [T). Note that our results can be generalized to the setting when is stochastic and outputs a probability distribution on U. Given MDP(XX, 4, T, P. c). we consider an optimization with time-varying costs and transition dynamics. Thus, our goal is to find a policy that minimizes the following expected total cost:
((x) = Ep,
Σ TE(T]
ci (Tt, Te (2x))
(I)
where the randomness in Ex is from the transition dynamies (P: (T)) and the policy (T, : [T]). We focus our analysis on the expected dynamic regret and the ratio of expectations, defined below, as the performance metrics for our policy design.
Definition (Expected dynamic regret), Given MDP UR,,U,, c). the (expected) dynamic regret of policy (Te it (TT) is defined as the difference between the expected cost induced by the policy n, J(x) in and the optimal expected cost J == inf, [z), ie., DR( = J(x) ) J
Dynamic regret is a more general (and often more challenging to analyze) measure than classical static regret, which has been mostly used for stationary environments 49 50 The following definition of the ratio of expectations [5] 22 results.
will be used as an alternative performance metric in our main
Definition 2 (Ratio of expectations). Given MDP(X. the ratio of expectations of policy x (Tz E (T]) is defined as RoE(T) == [J" where J(T) and J are the same as in
Definition
Dynamic regret and the ratio of expectations defined above also depend on the error of the untrusted ML advice; we make this more explicit in Section 3.2 Next, we state the following continuity assumption, which is standard in MDPs with continuous action and state spaces (3 55 our analysis can be readily adapted to general Hölder continuous costs with minimal modifications.
Note that
Assumption 1 (Lipschitz costs). For any time step t E [T), the cost cost function a X x + R. is Lipschitz continuous with a Lipschitz constant consttan Le < co, i.e., for any i. [T). |or(x u) aa u() s Le (||ær - x' I'Ilx + ||u w'llux). Moreover, O < ce(x, u) < xo for all I. E [T], x E X, and a E U
Consistency and Robustness in MDPs
Expected Robust Policy Black/Grey-BBa
Q-Value Advice Q₁
~ Suggested Action i,
Grey-Box
Black- Box
x,
π
ROB
U
Environment
Algorithm
Robust Policy
X,
Figure 1: Left: Overview of settings in problem. Right: consistency and robustness tradcoff, with RoE and s defined in Definition and Equation
Our objective is to achieve a balance between the worst-case guarantees on cost minimization in terms of dynamic regret provided by a robust policy, म, and the average-case performance of valued-based policy, म. in the context of MDP(XX, M, T. P.c). In particular, we denote by ROB 2 a ratio of expectation bound of the robust policy such that the worst case RoE(T) s ROB. In the learning- augmented algorithms literature, these two goals are referred to as consistency and robustness B... Informally, robustness refers to the goal of ensuring worst-case guarantees on cost minimization comparable to those provided by and consistency refers to ensuring performance nearly good as when से performs well (e-g., when the instance is not adversarial). seck to achieve consistency and robustness by combining ग and म. as illustrated in Figure |
Barning-augmenter algorithms

---

Table I:
Examples of models covered in this paper and the associated control baselines. For the right column, bounds on the ratio of expectations RoE are exemplified, where ROB is defined Section and O omits inessential constants.
Model
Robust Baseline
RoE
Time-varying MDP (Our General Model)
Wasserstein Robust Policy (Definition
ROB
Discrete MDP (Appendix A.2)
Any Policy that Induced a Regular Markov Chain MPC with Robust Predictions (Algorithm B
Tame-Varying LQR (Appendix A.1
O11)
Our focus in this work is to design robust and consistent algorithms for two types of advice: black-box advice and grey-box advice. The type of advice that nearly always the focus in the learning- augmented algorithm literature is black-bor box advice only providing a suggested action ūN without additional information. In contrast, on top of the action Ue grey-box advice can also reveal the internal state of the learning algorithm, e.g., the Q-value Qi in our setting. This contrast is illustrated in Figure I
Compared to black-box advice, grey-box advice has received much less attention in the literature, despite its potential to improve tradeoff's between consistency and robustness as recently shown in 34 77 Nonetheless, the extra information on top of the suggested action in grey-box setting algorithm to make a setter-informed decision based on the advice, thus achieving better tradeoff between consistency and robustness than otherwise possible.
potentially allows the
In the remainder of this section, we discuss the robustness properties for the algorithms we consider in our
framework (Section 3.T.. and introduce the notions of consistency in our
grey-hox and black-box models in Section 3.2
3.1 Locally Wasserstein-Robee Robust Policies
We begin with constructing novel notion of robustness for our learning-augmente framework based on the Wasserstein distance as follows. Denote the robust policy by मे := (T tt E [T]), where each T4 maps a system state to deterministic action (or probability of actions in the stochastic setting).
Denote by Ptystg (p) the joint distribution of the state-action pair (It, W&) E X x UI at time 12 E [7] when implementing the baselines T :T, consecutively with an initial state-action distribution p. We use xxxxu= == ||I Ilx + ||- llee as the included norm for the product space X' x U. Let W, (1, v) denote the Wasserstein p-distance between distributions μ and v whose support set is X' U::
Wyln, v) = (eeinnes S
[[a..)) - (x', ul) ((x, u), (1', (), ,d))
1/v
inf
where p E [1, 00) and J (H, v) denotes a set of all joint distributions J with a support set X' x U that have marginals y and v. Next, we define robustness condition for our framework.
Definition 3 (r-locally p- Wasserstein robustness). A policy गे (Te :tette E (TT) is r-locally p- Wasserstein-robut for any 0 S t1 t2 < T and any pair of state-action distributions p. p' where the the p- --assersttiin distance between them is bounded by Wplp, p') S r, for some radius O. the following inequality holds:
Wp (p), Pt (p') (6(12-4)W, (p.pl
for some function s: [T] + R4 satisfying Eie(T) s(t) < C. where C. > 0 is a constant.
Our robustness definition is naturally more relaxed than the usual contraction property in the con- trol/optimization literature 25 33 - if any two different state-action distributions converge expo- nentially with respect to the Wasserstein p-distance, then policy ग is r-locally p- -oosssssteein--buust. This is illustrated in Figure 2 Note that, although the Wasserstein robustness in Definition 3 well captures variety of distributional robustness metries such the total variation robustness de- fined on finite state/action spaces, it can also be further generalized to other metrics for probability distributions.
As shown Appendix (provided in the supplementary material), by establishing a connection between the Wasserstein distance and the total variation metric, any policy that induces regular
5

---

p
W, (ro((1))
W Wp
P
4
Figure 2: An illustration of r-locally p- wwwssesstein--obbie policy.
Markov chain satisfies the fast mixing property and the state-action distribution will converge with respect to the total variation distance to a stationary distribution [56]. A more detailed discussion can be found in Appendix A.2 Moreover, the Wassersteinn-rbustteess in Definition 3 includess set of contraction properties in control theory as special cases. For example, for a locally Wasserstein-robust policy, if the transition kernel P and the baseline policy т are deterministic, then the state-action distributions become point masses, reducing Definition to a state-action perturbation bound in terms of the 22-morm when implementing the policy т from different starting states
35 [9]
The connections discussed above highlight the existence of several well-known robust policies that satisfy Definition Besides the case of discrete MDPs discussed in Appendix A.2 another prominent example is model predictive control (MPC), for which robustness follows from the results in [19] (see Appendix
I. A.I for details). The model assumption below will be useful in our main results.
Assumption 2. There exists a 7ylocally p- --Wasserstein-oote robust baseline control policy (Definition for some p 2 1, where yy is the diameter of the action space U.
3.2 Consistency and Robustness for RoF
In parallel with the notation of "consistency and robustness" in the existing literature on learning-
augmented algorithms [ we define new metric of consistency and robustness in terms of RoE. To do so, we first introduce an optimal policy x². Based on MDP U, T, P. c). let कं = (m/ : E (7))
denote the optimal policy at each time step t E [2], whose optimal Q-value function
T
Q1 u) = inf Bp...
Σ
cr (Ir, ur)
r 2
where Ep,s denotes expectation with respect to the randomness of the trajectory {(x,, uz) :f [2'}} obtained by following a policy a and the transition probability at each step t E [T]. The Bellman optimality equations can then be expressed
(x, u) = (c. + V4+) u),
(i(())
inf (z, v), WEld
(i((x) = 0 (3)
for all (z, u) E X x u, L E [T] and E [T]. where we write (IP,V*) (z, u) == Exr [V*("'))
This indicates that for each time step L E [T]. पł the greedy policy with respect to its optimal Q-value functions (Q) 1 E []). Note that for any E [T]. (r, u) = 0. Given this setup, the
value-based policies ग. = (7, : E (T)) take the following form. For any E [7]. a value-based policy 7, X + U produces
action E arg min Qi (I,, v) by minimizing estimate of the optimal value function Qt.
We make the following assumption on the machine-learned untrusted policy से and the Q-value advice.
Assumption 3. The machine- learned untrusted policy मे is value-basede The Q-value advice QU X' x u + RR is Lipschitz continuous with respect to E U for any x E X, with Lipschitz constant Lo for all t (T). Moreover, Qt (x., u. Q (x, u) ((T) for all (x, u) E X x U and t (T).
We can now define a consistency measure for Q-value advice Q., which measures the error of the estimates of the Q-value functions due to approximation error and time-varying environments, etc. Letp E (0, xo). Fix a sequence of distributions p = (pt : E [T]) whose support set X' x U and let o be the marginal distribution of P: X. We define quantity representing the error of the Q-value

---

advice
<(p,
Σ (E(T)
(10.- Qi
inf Qe +
II
inf Qi
mp
well
pite
where || llp = (f (1|-(Pdy/ dp) 1/2 denotes the -orm. policy with Q-value functions (Q, : L [TT} is said to be (e, connsistent if there exists satisfying 4. In addition, a policy is (0, consssiittt if Q2 is a Lebesgue-meaauuabble function for all E [T] and (consssctn if the Loo -nom satisfies Eve(T) ll., - lo S E. The consistency error of a policy in quantifies how the Q-value advice close to optimal Q- functions. It depends on various factors such the function approximation error training error due the distribution shift, and has close connection to a rich literature on value function approximation (57-11. The results in [59] generalized the worst- case Loo guarantees to arbitrary -tp.rm under some mixing assumptions via policy iteration for a stationary Markov decision process (MDP) with a continuous state space and a discrete action space. Recently, approximation guarantees for the average case for parametric policy classes (such as a neural network) of value functions have started to appear (57 58 60) These bounds are useful in lots of supervised machine learning methods such classification and regression, whose bounds are typically given on the expected error under some distribution. These results exempliffy richer instances of the consistency definition (see 44) and summary of these bounds can be found in [6].
Now, we are ready to introduce our definition of consistency and robustness with respect to the ratio of expectations, similar to the growing literature on saaming-auggeent algorithms E 22 23) 4
We write the ratio of expectations RoE(s) of a policy æ as function of the Q-value advice error in terms of the Lo norm, defined in
Definition 4 (Consistency and Robustness). An algorithm a is said to be k-consistent if its worst-case (with respect to the MDP model MDP 11, T, P.))) ratio of expectations satisfies RoE(s) S k for E = O. On the other hand, it (-robust if RoE(s) S L for any E O.
The Projection Pursuit Policy (PROP)
In this section we introduce our proposed algorithm (Algorithm) D. which achieves near-optimal con- sistency while bounding the robustness by leveraging a robust baseline (Section 3.T in combination with value-based advice (Section (.2). A key challenge in the design is how to exploit the benefits of good value-based advice while avoiding following it too closely when it performs poorly. To address this challenge, we propose to judiciously project the value- based advice into neighborhood of the robust baseline. By doing so, the actions we choose can follow the value-based advice for consistency while staying close to the robust baseline for robustness. More specifically, at each step E [T), we choose i, Projz, (ū+) where a projection operator Projez, (.) 2 + U1 is defined as
Projz, (u) == arg min I|u - vllee subject to || - गe (2:) S Re, eEul
(5)
corresponding the projection of onto ball 77 {u U =1 S Re). Note that when the optimal solution of (5) is not unique, we choose the one on the same line with क, (xx) u.
The PROjection Pursuit policy, abbreviated as PROP, can be described follows. For a time step t E [T'. let म. X' + Z2 denote policy that chooses an action ū, (arbitrarily choose one if there are multiple minimizers of Q:), given the current system state I; at time & E [T'] and step & E [7]. An action un = Proju, (āe (xx)) selected by projecting the machine-learned action (xx) onto
norm ball U, defined by the robust policy given radius R2 > 0. Finally, PROP applies to both black-box and grey-box settings (which differ from each other in terms of how the radius RG is decided). The results under both settings are provided in Section 5 revealing a tradeoff between consistency and robustness.
The radii (R, : t E (T]) can be interpreted as robustness budgets and are key design parameters that determine the consistency and robustness tradeoff. Intuitively, the robustness budgets reflect the trustworthiness on the value-based policy मे - the larger budgets, the more trustworthiness and hence the more freedom for PROP to follow How the robustness budget is chosen differentiates the grey-box setting from the black-box one.
7

---

Algorithm/ 1 PROjection Pursuit Policy (PROP)
Initialize Untrusted policy मे (it E (2]) and baseline policy म (Te t [7])
for t O,...,T do
2
//mplement black-box (Section 4.1 or grey-box (Section
procedures
(ūe, Ri) BLACK (z or ( R₂) GREY-BOX(
4
Set action un = Proju, (ūt) where Ue = {u E u 1|u R (ze)llu - R
5
Sample next state 21+1 ~ Pt (-12e, u.)
end
4.1 Black-Box Setting
In the black-box setting, the only information provided by मे is a suggested action ö for the learning- augmented algorithm. Meanwhile, the robust policy тे can also be queried to provide advice H. Thus, without additional information, natural way to utilize both से and हे is to decide projection radius at each time based on the how the obtained 2 and T. More concretely, at each time t E [T]. the robustness budget R, is chosen by the following
BLACK-BBX Procedure, where we set R₂ An with 7)t := || ue Eilzz representing the difference between the two advice measured in terms of the norm || I1u and 0 < x < 1 being tradeoff hyper-parameter that measures the trustworthiness on the machine-learned advice. The choice of R. = Arp: can be explained as follows. The value of Ne indicates the intrinsic discrepancy between the robust advice and the machine-learned untrusted advice - the larger discrepancy, the more difficult to achieve good consistency and robustness simultaneously. Given robust policy and an untrusted policy, by setting larger X, we allow the actual action to deviate more from the robust advice and to follow the untrusted advice more closely, and vice versa. À is a crucial parammee that can be pre-determined yield desired consistency and robustness tradeoff. The computation of Re is summarized in Procedure | below.
Procedure BLACK-BoO -Bo Procedure at E [T'] (Input: state H, and hyper-parameter S À A 1)
Implement मे and T. to obtain ün and üy respectively.
Set robustness budget Re = ATy where 7): = || ūt li Return (ūe, Re)
4.2 Grey-Box Setting
In the grey-box setting, along with the suggested action ū, the value-based untrusted policy से also provides an estimate of the Q-value function Q that indicates the long- long-term cost impact of an action. To utilize such additional information informed by Qe at each time & [T]. we propose novel algorithm that dynamically adjusts the budget Rs to further improve the consistency and robustness tradcoff. More concretely, let us consider the Remporal-Differenee Intuitively, if a nor-zero TD-error is observed, the budget R, needs to be decreased so as to minimize the impact of the learning error. However, the exact TD-error is difficult to compute in practice, since it requires complete knowledge of the transition kernels (P, t E (T)). To address this challenge, we use the following estimated TD-error based on previous trajectories:
(TD) error TD, Q-1 + P Vv Q
8z (I1, Ft-1, 14 14-1) =0-1 (#t-1; 14-1) + inf Q (Iz, v) - -Q--1 (Ft-1,
(6)
well
Denote by 8 >>> 0 a hyper Based on the estimated TD-error in 6 the robustness budget in Algorithm M is set as
B
R₂ ==
me (Ix) - Te (mo)
8g (Wis Fe- Wa-1)
L
Decision Discrepancy
Approximate TD-Error
which constitutes two terms. The first term 7/- := || (xx.) (xt) measures the decision discrep- ancy between the untrusted policy 7 and the baseline policy n, which normalizes the total budget, similar to the one used in the black-box setting in Procedure I The second term is the approximate TD-error, which is normalized by the Lipschitz constant LQ of Q-value functions. With these terms defined, the GREY-BOX Procedure below first chooses suggested action ū, by minimizing Q, and then decides a robustness budget Rd using
8

---

Procedure 2 GREY-BOX Procedure at E [7) (Input: state and hyper-parameter < 11)
Obtain advice Qe and dn where ūy arg oet4 Qt (2t, v) Implement n and obtain 1t Set robustness budget Rg as 7 Return (ū,, R,)
5
Main Results
We now formally present the main results for both the black-box and grey-box settings. Our results not only quantify the tradeoffs between consistency and robustness formally stated in Definition with respect to the ratio of expectations, but also emphasize crucial role that additional information about the estimated Q-values plays toward improving the consistency and robustness tradeoff.
5.1 Black- Box Setting
In the existing learning- -aggenetee algorithms, the untrusted machine-learned policy म is often treated as a black-box that generates action advice ün at each time i E T Our first result is the following general dynamic regret bound for the black-box setting (Section denoted as (-) and o(-) to disregard inessential constants.
We utilize the Big-O notation,
Theorem 5.1. Suppose the machine-learned policy is (oo,e)-consister For any MDP model satisfying Assumption 2 and 3 the expected dynamic regret of PROP with the BLACK-BOX Procedure is bounded by DR(PROP) S min(O(e) + O( - X)TT), ((ROB + >y - 1) where is defined in ④ y is the diameter of the action space U. T is the length of the time horizon, ROB is the ratio of expectations of the robust baseline n, and 0 < X S 1 is
When À increases, the actual action can deviate more from the robust policy, making the dynamic regret potentially closer to that of the value-based policy. While the regret bound Theorem [. clearly shows the role of À in terms of controlling how closely we follow the robust policy. the dynamic regret given a fixed À E [0, 1] grows linearly in (T). In fact, the linear growth of dynamic regret holds even if the black-box policy से is consistent, i.e., is small. This can be explained by noting the lack of dynamically tuning À to follow the better of the two policies - even when one policy is nearly perfect, the actual action still always deviates from it due the fixed choice of X.
Consider any MDP model satisfying Assumptions 12 and Following the classic definitions of consistency and robustness (see Definition 4. we summarize the following characterization of PROP, together with a negative result in Theorem Proofs of Theorem 5.1 5.2 and 5.3 are detailed in Appendix C
Theorem 5.2 (BLACK- -Bx Consistency and Robustness). PROP with the BLACK-BOX Procedure
(1 + ((1 {)7)) -oosssctt and (ROB + 0(Xr)))robuss where
< is hyper-parameter.
Theorem 5.3 (BLACK-Bol Box Impossibility). PROP with the BLACK-Bol Procedure cannot be both (1 + o((1 A)r)) ()))))-cosssstte consistent and (ROB + o(Ar))) any 0 < X 1
5.2 Grey-Box Setting
To overcome the impossibility result in the black-box setting, we dynamically tune the robustness budgets by tapping into additional information informed by the estimated Q-value functions using the
GREY-BOX Procedure (Section 4.2) By setting the robustness budgets in 7 an analogous result of
Theorem 5.1 is given in Appendix D which leads a dynamic regret bound of PROP in the grey-box
12 and Our main result below indicates that knowing more structural information about black-box policy can indeed bring additional benefits in terms of the consistency and robustness tradeoff, even if the black- policy is untrusted.
setting hhorem D. in Appendix D. Consider any MDP model satisfying Assumptions
Theorem 5.4 (GREY-Bor Consistency and Robustness). PROP with the GREY-BOX Procedure is 1-consistent and (ROB + rob))-tobust for some / > 0.
Theorem 5.3 implies that using the BLACK-Box Procedure, PROP cannot be 1-consistent and (ROB + o o()) -robust, while this can be achieved using the GREY-BOX Procedure, On one hand, this theorem validates the effectiveness of the PROP policy with value-based machine-learned advice that

---

may not be fully trusted. On the other hand, this sharp contrast between the black-box and grey-bor settings reveals that having access information of value function can improve the tradeoff between consistency and robustness (see Definition 4 non-trivially. A proof of Theorem 5.4 can be found in Appendix Applications our main results are discussed in Appendix A
Concluding Remarks
Our results contribute to the growing body of literature on learning auggmnted algorithms for MDPs and highlight the importance of considering consistency and robustness in this context. In particular, we have shown that by utilizing the structural information of machine learning methods, is possible to achieve improved performance over black-box approach. The results demonstrate the potential benefits of utilizing value-based policies as advice; however, there remains room for future work in exploring other forms of structural information.
Limitations and Future Work. One limitation of our current work the lack of analysis of more general forms of black-box procedures. Understanding and quantifying the available structural information in a more systematic way another future direction that could lead advances in the design of learning-augnin augmented online algorithms and their applications in various domains.
Acknowledgement
We would like to thank the anonymous reviewers for their helpful comments. This work was supported part by the National Natural Science Foundation of China (NSFC) under grant No. 72301234 the Guangdong Key Lab of Mathematical Foundations for Artificial Intelligence, and the start-up funding UDF01002773 of -Shennhhen Yiheng Lin was supported by the Caltech Kortschak Scholars program. Shaolci Ren was supported in part by the U.S. U.S. National Science Foundation (NSF) under grant CNS-191022 Adam Wierman was supported in part by the U.S. NSF under grants CNS-2146814 CPS-2136197, CNS-2106400 NGSDI-2105644
References
[1] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65(7):33 2022.
[2] Tongxin Li. Bouriing-Augennter Control and Decision-Making: Theory and Applications in Smart Grids. PhD thesis, California Institute of Technology, 2023.
[3] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018.
[4] Nicolas Christianson, Tinashe Handina, and Adam Wierman. Chasing convex bodies and functions with black-box advice. In Conference on Learning Theory, pages 867-908. PMLR, 2022.
[5] Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances in neural information processing systems, 30, 2017.
[6] Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. On function approximation in reinforcement learning: optimism in the face of large state spaces. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 13903-139 13910. 2020.
[7] Noah Golowich and Ankur Moitra. Can gelearning be improved with advice? In Conference on Learning Theory, pages 4548 4619, PMLR, 2022.
[8] Chen- Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: optimal black-bor approach. In Conference on Learning Theory, pages 4300-4354, PML.R, 2.21.
10

---

[9] Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Basar. Near Near-opting optimal model-free reinforcement learning non-stationary episodic mdps. International Conference on Machine Learning, pages 7447-7458. PMLR, 2021.
[10] Yuwei Luo,, Varun Gupta, and Mladen Kolar. Dynamic regret minimization for control of non- stationary linear dynamical systems. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(1):1-72, 2022.
[11] Peng Zhao, Long-Fei Li, and Zhi-Hua Zhou. Dynamic regret of online markov decision processes. In International Conference on Machine Learning, pages 2022.
PMLR,
[12] Christian Scheller, Yanick Schraner, and Manfred Vogel. Sample efficient reinforcement learning through learning from demonstrations in minecraft. In NewrlPS 2019 Competition and Demonstration Track, pages 67-76. PMLR, 2020.
[13] Matthew Botvinick, Sam Ritter. Jane X Wang. Zeb Kurth-Nelson, Charles Blundell, and Demis Hassabis. Reinforcement learning, fast and slow. Trends in cognitive sciences, 23(5):408-422 2019.
[14] Xueying Bai, Jian Guan, and Hongning Wang. A model-based reinforcement learning with adversarial training for online recommendation. Advances in Neural Information Processing Systems, 32, 2019.
[15] Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. Advances in Neural Information Processing Systems, 33:20636-206s 20647,, 2020.
[16] Gautam Goel and Babak Hassibi. Competitive control. IEEE Transactions on Automatic Control, 2022.
[17] Tongxin Li, Ruixiao Yang, Guannan Qu, Guanya Shi, Chenkai Yu, Adam Wierman, and Steven Low. Robustness and consistency in linear quadratic control with untrusted predictions. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(1):1-35, 2022.
[18] Oron Sabag, Sahin Lale, and Babak Hassibi. Optimal competitive-ratio control. arXiv preprint 2rX.v:2206.01782, 2022.
[19] Yiheng Lin, Yang Hu, Guannan Qu, Tongxin Li, and Adam Wierman. Bounded-regret mpc via perturbation analysis: Prediction error, constraints, and nonlinearity. Advances Neural Information Processing Systems, 35:36174-36187, 2022.
[20] Tongxin Li, Yue Chen, Bo Sun, Adam Wierman, and Steven H Low. Information aggregation for constrained online control. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(2):1-35, 2021.
[21] Tongxin Li, Bo Sun, Yue Chen, Zixin Ye, Steven H Low, and Adam Wierman. Learning- based predictive control via real-time aggregate flexibility. IEEE Transactions on Smart Grid, 12(6):4997-4913 2021.
[22] Alexander Wei and Fred Zhang. Optimal robustness-consisteee trade-offs for learning- augmented online algorithms. Advances in Neural Information Processing Systems, 33:8042- 8053, 2020.
[23] Shom Banerjee. Improving online rent-or-buy algorithms with sequential decision making and ml predictions. Advances in Neural Information Processing Systems, 33:21072-21080, 2020.
[24] Stephen Tu, Alexander Robey, Tingnan Zhang, and Nikolai Matni. On the sample complexity of stability constrained imitation learning. In Learning for Dynamics and Control Conference, pages 180-191. PMLR, 2022.
[25] Hiroyasu Tsukamoto, Soon-Jo Chung, and Jean-Jaques E Slotine. Contraction theory for nonlinear stability analysis and learning-based control: tutorial overview, Annual Reviews in Control, 52:135-169, 2021.

---

[26] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Online optimization with uncertain information, ACM Transactions on Algorithms (TALG). 8(1):1-29, 2012.
[27] Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1834-1845. SIAM, 2020.
[28] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1-25, 2021.
[29] Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. Parsimonious learning-augmented caching. In International Conference on Machine Learning, pages 9588 1888-660. PMLR, 2022.
[30] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In International Conference Machine Learning, pages 345-355. PMLR, 2020.
[31] Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems, 33:20083-20093 2020.
[32] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions, In International Conference on Machine Learning, pages 582-598. PMLR, 2022.
[33] Tongxin Li, Ruixiao Yang. Guannan Qu, Yiheng Lin, Adam Wierman, and Steven H Low. Certifying black-bos policies with stability for nonlinear control. IEEE Open Journal of Control Systems, 2023.
[34] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In International Conference on Machine Learning. pages 2687-2696. PMLR, 2021.
[35] Yiheng Lin, Yang Hu, Guanya Shi, Haoyuan Sun, Guannan Qu, and Adam Wierman. Perturbation-basee regret analysis of predictive control in linear time varying systems. Advances in Neural Information Processing Systems, 34:5174-518 2021.
[36] Yiheng Lin, Yang Hu, Guannan Qu, Tongxin Li, and Adam Wierman. Bounded-regret mpe via perturbation analysis: Prediction error, constraints, and nonlinearity. In Advances in Neural Information Processing Systems, 2022.
[37] David Hoeller, Farbod Farshidian, and Marco Hutter. Deep value model predictive control, In Conference on Robot Learning, pages 990-1004. PMLR, 2020.
[38] Richard Cheng, Abhinav Verma, Gabor Orosz, Swarat Chaudhuri, Yisong Yue, and Joel Burdick. Control regularization for reduced variance reinforcement learning. In International Conference on Machine Learning, pages 1 1151-1150. PMLR, 2019.
[39] Lukas Brunke, Melissa Greeff, Adam W Hall, Zhaocong Yuan, Siqi Zhou, Jacopo Panerati, and Angela P Schoellig. Safe learning in roboties: From learning-based control to safe reinforcement learning. Annual Review of Control, Robotics, and Autonomous Systems, 5:411 2022.
[40] Lin Guan, Mudit Verma, Suna Sihang Guo, Ruohan Zhang, and Subbarao Kambhampati. Widening the pipeline in human-guided reinforcement learning with explanation and context- aware data augmentation. Advances in Neural Information Processing Systems, 34:21885- 21897, 2021.
[41] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
[42] James MacGlashan, Mark K Ho, Robert Loftin, Bei Peng, Guan Wang, David L Roberts, Matthew Taylor, and Michael I. Littman. Interactive learning from poleey-dependent human feedback. In International Conference on Machine Learning, pages 2285-2294 PMLR, 2017.
12

---

[43] Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, pages 10835-10866 PMLR, 2023.
[44] Felix Berkenkamp, Matteo Turchetta, Angela Schoellig, and Andreas Krause. Safe model-based reinforcement learning with stability guarantees. Advances neural information processing systems, 30, 2017.
[45] Mengdi Xu, Zuxin Liu, Peide Huang, Wenhao Ding, Zhepeng Cen, Bo Li, and Ding Zhao. Trustworthy reinforcement learning against intrinsic vulnerabilities: Robustness, safety, and generalizability. arXiv preprint arXiv:2209.08025, 2022.
[46] Matthew E Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey, Journal of Machine Learning Research, 10(7), 2009.
[47] Irina Higgins, Arka Pal, Andrei Rusu, Loic Matthey, Christopher Burgess, Alexander Pritzel, Matthew Botvinick, Charles Blundell, and Alexander Lerchner. Darla: Improving zero-shot transfer in reinforcement learning. In International Conference Machine Learning, pages 1480-1490. PMLR, 2017.
[48] Elynn Y Chen, Michael I Jordan, and Sai Li. Transferred q-learning. arXiv:2202.04709 2022.
arXiv preprint
[49] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
[50] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017.
[51] Allan Borodin and Ran El- Yaniv. Online computation and competitive analysis. cambridge university press, 2005.
[52] Nikhil R Devanur and Thomas P Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce, pages 71-78, 2009.
[53] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference Machine Learning, pages 111-119. PMLR, 2019.
[54] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pages 2681 1691.. PMLR, 2019.
[55] Paula Gradu, John Hallman, and Elad Hazan. Non-stochastic control with bandit feedback. Advances in Neural Information Processing Systems, 33:10764-10774 2020.
[56] Sheldon M Ross. Stochastic processes. John Wiley & Sons, 1995.
[57] Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming: overview. In Proceedings of 1995 34th IEEE conference on decision and control, volume 1. pages 560-564. IEEE, 1995.
[58] Rémi Munos. Enror bounds for approximate policy iteration. In ICML, volume 3, pages 560-567. Citeseer, 2003.
[59] András Antos, Csaba Szepesvári, and Rémi Munos. Learning optr-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71(1):89-129 2008
[60] Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning, pages 2160-2169. PMLR, 2019.
13

---

[61] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22(98):1-76, 2021.
[62] Yiheng Lin, James A Preiss, Emile Timothy Anand, Yingying Li, Yisong Yue, and Adam Wierman. Online adaptive policy selection vir-ingying systems: No-regret via contractive perturbations. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
[63] Runyu Zhang, Yingying Li, and Na Li. On the regret analysis of online LQR control with predictions, In 202/ American Control Conference (ACC), pages 697-703. IEEE, 2021.
[64] James R Norris. Markov chains. Cambridge university press, 1998.
[65] Steve Lalley. Markov chains: Basic theory. https://ggatton wdw.aaaao.euuaaaalaaa Moorsess/112/aaroovchiaasss, pdf 2016.
[66] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
[67] Yingying Li and Na Li. Online learning for markov decision processes in nonstationary environments: A dynamic regret analysis. In 20/9 American Control Conference (ACC), pages 1232-1237. IEEE, 2019.
[68] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jic Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: arXiv:1606.000 (666601540, 2016.
[69] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning. pages 387-395. Pmir, 2014.
[70] Leonid Kantorovitch. On the translocation of masses. Management science, 5(1):1-4, 1958.
[71] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference International Conference Machine Learning, pages 1015-1022, 2010.
14


Reviews:
[{"review_id": "FM6WwiS1rw", "reviewer": "Reviewer_c87H", "summary": "Authors study algorithms for Marcov Decision Processes receiving advice in the\nform of a value-based machine-learned policy. Value-based policies decide\ntheir actions based on minimizing an estimated Q-function, which predicts\nthe best possible outcome in the rest of the time horizon given a current\naction. Such policies are known to perform well in some practical scenarios,\nbut collapse in others.\n\nThey propose algorithms for two regimes. In the first regime, the algorithm\nreceives only the action taken by the value-based policy while, in the\nsecond regime, it also receives an estimate of the Q-function used by the\nvalue-based policy to determine its action.\nIn the first regime, they propose a consistency-robustness tradeoff.\nIn the second regime, they use the additional information (Q-function) to\nestimate the quality of the advice provided by the value-based policy\nand tune the trade-off parameter online, obtaining consistency 1 and\nnear-optimal robustness.\nThey show that the analysis of their algorithm for the first regime is tight.\n", "questions": "* In algorithm 1, should line 6 be part of the for loop?", "limitations": "their ML-augmented algorithms are limited to a certain kind of predictions. Authors have mentioned this limitation clearly in the last section of their submission.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* work on an important problem\n* online tuning of the consistency-robustness trade-off\n* tight analysis of their algorithm", "weaknesses": "* It is not clear whether consistency-robustness tradeoff with weaker predictions is necessary for any algorithm. They prove a lower bound only for their algorithm.\n* requires machine-learned advice in a form of a value-based policies. Other kinds of policies might be also beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you so much for the valuable feedback on our work!  Below are our responses to the comments:\n\n1. **Consistency-Robustness Tradeoff for Black-Box Setting**:\n\n>*It is not clear whether consistency-robustness tradeoff with weaker predictions is necessary for any algorithm. They prove a lower bound only for their algorithm.*\n\nWe appreciate a lot your thoughtful observation regarding the necessity of the consistency-robustness tradeoff with weaker predictions for any black-box algorithm, as we mentioned in the limitation. \n\nThe lower bound we have is for a special black-box procedure, which convexly combines actions given by the machine-learned policy and the robust baseline. Although this form is special, it has been widely used to design controllers such as in references [16] and [35] in the manuscript. \n\nOur main results show that additional \"grey-box\" advice (Q-values) can indeed be used to nontrivially improve the consistency and robustness tradeoff such that with the grey-box advice, we can actually do better than the best that we can hope for in the considered black-box setting, i.e., better than the lower bound in the black-box setting. \n\nWe acknowledge that this point might not have been explicitly articulated in the paper, and we will revise the manuscript accordingly to provide clearer context. \n\n2. **Beyond Value-Based Policies**:\n\n>*It requires machine-learned advice in a form of a value-based policies. Other kinds of policies might be also beneficial.*\n\nThank you for bringing up the concern! \n\nIt's important to note that our findings provide insights into the potential benefits of going beyond the pure black-box setting by incorporating other forms of advice in decision-making processes, resulting in near-optimal performance guarantees in the general MDP setting. Our current results focus on the specific case of machine-learned advice in the form of value-based policies, specifically Q-value advice. \n\nDespite this limitation, the class of value-based policies is still an important type of policies to consider. We chose this setting to investigate the tradeoff between consistency and robustness to highlight the advantages of leveraging additional information about how the advice is generated. While our current analysis focused on value-based policies, the implications of our work extend to the broader understanding of optimally using machine-learned advice for decision-making tasks. \n\nCurrently, we acknowledge that there are other forms of policies that could be beneficial and might influence the consistency-robustness tradeoff differently. For example, policy-gradient-based approaches, model-based policies (knowledge of the model could be some grey-box information), or even ensemble methods could be relevant alternatives that deserve exploration in future research. As future works, it would be interesting to fully understand the impact of information from machine-learned algorithms by exploring and unifying  other forms of advice.\n\n\n3. **Line 6 in Algorithm 1**:\n\n>*In algorithm 1, should line 6 be part of the for loop?*\n\nThank you so much for pointing out this typo! We have fixed it in the revised manuscript."}, {"review_id": "AL6NUojE3y", "reviewer": "Reviewer_9C69", "summary": "This paper provides a theoretical study of the tradeoff between consistency and robustness in Markov Decision Process for which machine learned advice is available. With extensive theoretical analyses, the paper leverages Q-value advice for improving the impact of machine-learned advice in these contexts. Several hyperparameters are suggested which control the impact of these learned advices. The paper provides derivations for both black-box and grey-box settings. \n\n\nI have read the rebuttal. I am more positive about this submission after the rebuttal and reading the other reviews.The authors have addressed my concerns regarding empirical validation, and the lack of practical examples.", "questions": "- L 308: What is the impact of this approximation? \n- L 283: Could you give a practical example of the impact of this radii?", "limitations": "Limitations and the broader impact of this method are properly addressed.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper studies an interesting and salient problem and provides theoretical derivations for their findings. \n- The paper is clearly structured. \n- Limitations and broader impact are adequately studied. \n- Supplementary material is impressively extensive and detailed.", "weaknesses": "- I believe the paper could strongly benefit from empirical validation to better communicate the potential impact of their theoretical findings. \n- Some decision choices (see Questions) require further discussion.\n- This paper is at times hard to follow and could be written in a more clear way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments! Below are our responses to your specific comments and questions:\n\n1. **Empirical Validation**: \n\nWhile our primary focus and main contribution center around the theoretical aspects, we fully agree with your suggestion that empirical validation can significantly enhance the manuscript's impact and better communicate the potential implications of our theoretical findings.\n\nIn the revised manuscript, we will add some empirical results in the appendix to further demonstrate the applicability of our methods in real-world settings. \n\n2. **Impact of Approximation**: \n\n>*What is the impact of this approximation?*\n\nOur algorithm relies on the estimated TD-error in equation (6). In our approach, the \"robustness budget\" $R_t$ is set according to equation (7), utilizing the estimated TD-error. This is because computing the true TD-error requires knowledge of the transition probabilities in the MDP, which is often not feasible. \n\nThroughout our analysis, we select $R_t$ as specified in equation (7). To handle the approximation error in our analysis, we introduce an additional technical lemma (Lemma B.3). of the supplementary material, which plays a crucial role in accounting for approximation errors. The key idea is to decompose the estimated TD-error into two terms representing the differences between Q-values. The proof is given in Appendix B.\n\n3. **Practical Examples**: \n\n>*Could you give a practical example of the impact of this radii?*\n\nBelow we use two real-world examples to demonstrate the impact of the radii (line 283).\n\n*A. Voltage Control.* Consider a practical scenario where we need to control an inverter in a power system to regulate voltage. The control action involves adjusting the reactive power. Considering the injections from renewable resources, the control dynamics can be formulated as an MDP.\n\nRecent research has shown promising results in using learning-based methods, such as RL or multi-agent RL, to control inverters in power systems [Marot et al.], [Wang et al.]. However, a major challenge arises when applying these methods to real systems, as they may suffer performance degradation when the environment changes, such as seasonal variations, human behaviors, policy changes, or extreme weather conditions. Safe RL methods [Sootla et al.] or specific neural network designs [Chen et al.] can provide guarantees of feasibility, but they may still fall short of optimal performance during distribution shifts, particularly when the MDP becomes non-stationary.\nExisting baseline methods, such as droop control, have been used for voltage and frequency control problems in power systems. However, these methods may not fully leverage the benefits of learning-based approaches.\n\nOur proposed methods offer a potential solution to bridge this gap. We can regulate the flexibility of the true actions to align with machine-learned actions centered at the Wasserstein robust actions. A larger radius indicates greater trust in the machine-learned actions, allowing the inverter control to follow the RL action and vice versa. By tuning the radii and finding the optimal balance between robustness and consistency, we can enhance the efficiency and reliability of inverter control in the face of dynamic and uncertain power system environments. \n\n*A. Autonomous vehicle Navigation.* Another example is in the context of autonomous driving. Imagine an autonomous vehicle navigating through a busy city. The vehicle's decision-making system relies on a mix of a pre-trained value-based policy and a baseline navigator based on external sources (e.g., traffic lights and pedestrian movements from the vehicle sensors).\n\nIn this scenario, a small radius would mean the autonomous vehicle relies heavily on the baseline signals and is less willing to trust the machine-learned policy. This could lead to a safer but conservative plan, where the vehicle may miss opportunities to navigate through traffic more efficiently, especially during rush hours when traffic patterns are complex. On the other hand, a larger radius would imply the autonomous vehicle is more willing to trust the value-based policy . \n\nChoosing an appropriate radius implies a delicate balance. If the radius is too small, the vehicle may not fully utilize valuable action from the value-based policy, missing opportunities for efficient navigation. If the radius is too large, it may rely excessively on potentially untrustworthy advice, compromising the reliability. By characterizing how Q-value advice can improve the consistency and robustness tradeoff, the radii determined by the approximate TD-error offer provable solutions to strike the right balance. Optimally setting these radii ensures the autonomous vehicle can effectively integrate its own learned policy and the baseline signals, leading to safer, more efficient, and reliable autonomous driving behavior. We will clarify in the revised manuscript using these concrete applications to improve the readability.\n\n4. **Paper is Hard to Follow**. Thank you for bringing out this issue! We will improve the readability of the paper by furnishing more practical examples as aforementioned and provide more and better explanations. \n\n**References**\n\n[Marot et al.] Marot, Antoine, et al. \"Learning to run a power network challenge: a retrospective analysis.\" NeurIPS 2020 Competition and Demonstration Track. PMLR, 2021.\n\n[Wang et al.] Wang, Jianhong, et al. \"Multi-agent reinforcement learning for active voltage control on power distribution networks.\" Advances in Neural Information Processing Systems 34 (2021): 3271-3284.\n\n[Sootla et al.] Sootla, Aivar, et al. \"Sauté rl: Almost surely safe reinforcement learning using state augmentation.\" International Conference on Machine Learning. PMLR, 2022.\n\n[Chen et al.] Chen, Yize, et al. \"Optimal Control Via Neural Networks: A Convex Approach.\" International Conference on Learning Representations. 2019."}, {"review_id": "UW557p8iWm", "reviewer": "Reviewer_BSCA", "summary": "This paper investigates ways to combine untrusted learned policy and Q value predictions with a trusted baseline fixed policy such that the resulting combination achieves a higher performance bound and lower regret than established methods for combining the two. In particular, this paper studies how the use of Q-value predictions in addition to policy action predictions allows for stronger robust performance.", "questions": "Thinking out loud, I wonder if relative TD error (compared to some MDP-specific baseline or a running average or similar) might make more sense in practice for equation 6 given the challenges introduced by deep RL models and MDP-specific scale variance. Relative TD error prioritization has been used for both prioritized experience replay and exploration, so there's evidence in deep RL that this sort of ranked/relative error measure is at least semi-reliable.\n\nRegarding using various forms of structural information/error signals for RL, it might be useful for future work to look at some of the literature on exploration and robust/safety-conscious RL (if the authors are not already familiar with this literature) and how novelty/uncertainty metrics are used in those fields. A wide range of metrics have been proposed with differing tradeoffs which might be theoretically useful or at least provide inspiration.\n", "limitations": "While I can't speak well to the theoretical limitations of this paper, I have some discussion of possible practical limitations in the above sections (though such concerns are out of scope for this paper).\n\nI don't see any potential negative societal impact from this paper. I will note the authors include a consideration of the potential impacts at the bottom of the paper regardless, which is pleasant to see.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I'll first state that that my expertise is in the field of experimentally-driven deep reinforcement learning, so as this paper seems to come from the control-theory literature my ability to evaluate some aspects of it and to properly value its contribution to that field is limited. As such I will focus my comments on the elements where I can speak with some confidence and give the benefit of the doubt regarding other aspects (particularly the overall significance and originality of the problem and set of assumptions being made to the control theory community).\n\nAll that said, from my perspective, this paper makes a lot of sense- the core argument, that using information about TD error (or more generally the error estimates of the RL model- I can imagine there's ways to extend this work to other flavors of RL algorithms without Q-functions) allows for a better tradeoff between consistency and robustness, seems like a sensible one. \n\nIn deep RL it's common to use various measures of model error/confidence to constrain the actions and/or gradient updates of the model in a less rigorous way (Conservative Q Learning is a recent notable example of this), so doing the same thing to bound robustness guarantees makes sense to me.\n\nDespite the difference in field, this paper communicated well and got the core arguments and algorithms across, and seems well written in general, though I can't comment on the perspective of a control theorist on this point.", "weaknesses": "To err on the side of generosity, I'm going to use this section to mostly speak to the practical feasibility and relevance of this paper (at least my sense of it). It's a theory paper, so I don't consider any of this a critical flaw in the work, but hopefully this is a useful perspective for the authors in their future work. \n\nI'm unsure if assumption 3 is reasonable by default- it might require a very large Lipschitz constant for most neural network architectures (not an expert on this, but my understanding is most common architectures have very poor guarantees on curvature). While theoretically valid I worry that it might require the use of specialized models to get a reasonable constant in practice, especially since per equation 7 it looks like a specific value is needed for normalization, so there's incentive to use as small a number as possible.\n\nThe approximate TD error in equation 6 makes sense to use as an approximate trust measure, but I'll caution that in practice the magnitude of these values can vary by orders of magnitude and is highly MDP dependent, so there may be MDP/model dependent scale/normalization hyperparameters that need to be introduced. In theory and principle it makes sense to me, but my sense is that further work is needed to make this measure practical. \n\nAnother limitation might be applicability in contexts that are very different from those in which the Q-function was trained. Assuming the immediate reward/cost is not available or not highly informative (for example, if we have a lot of deferred and/or sparse rewards) and that the model is not being finetuned, in such cases the TD error between Q_t and Q_t+1 could be small despite the model being highly inaccurate in its Q estimates and thus its actions might be highly untrustworthy. \"Confident but wrong\" is a sadly common phenomenon in deep RL.\n\nOverall though I don't think these issues are immediately relevant to the significance of this work, due to being both out of scope and possible to address through future work. As such (and being deferential regarding significance and novelty since I can't comment on those well) I'm inclined to recommend acceptance for this paper, subject to the opinions of other reviewers who may have perspective I lack.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for the thorough review and the valuable insights provided. Your positive evaluation from a experimentally-driven deep RL perspective of the core argument regarding the derived tradeoff between consistency and robustness using TD error information is very encouraging.\n\nRegarding the concerns you raised about practical feasibility and relevance, we will consider adding some more concrete examples and empirical validations to demonstrate the efficacy of the proposed method. While our main focus is to understand theoretically how to go beyond the pure black-box setting and understand the fundamental tradeoff between consistency and robustness, we agree that the aspects mentioned by the reviewer are all important to consider. Let us address these points:\n\n1. **Assumption 3**: \n\n>*I'm unsure if assumption 3 is reasonable by default- it might require a very large Lipschitz constant for most neural network architectures. While theoretically valid I worry that it might require the use of specialized models to get a reasonable constant in practice.*\n\nGuaranteeing a small Lipschitz constant can indeed be a practical concern for most neural network architectures. While we provided a theoretical basis for this assumption, we understand that in practice, obtaining a suitable constant $L_Q$ may be challenging and this depends on how the values functions are parameterized. To address this, we will discuss this limitation explicitly in the paper and highlight the need for further investigation into selecting or approximating the Lipschitz constant in practical scenarios. \n\nBesides, such a continuity assumption on the Q-value functions is common in the related literature. For example, similar assumption has been used to deal with the general continuous MDP in off-policy evaluation by using the Lipschitz property of the Q-functions [Tang et al.]. \n\nIt is worth mentioning that there is a line of works [Hinderer et al.], [Asadi et al.] that have studied the necessary Lipschitz smoothness conditions on the transition and reward functions, to make the value functions Lipschitz. Besides these conditions, as shown in [Gelada et al.], a parameterized\nlatent space model (called DeepMDP) can be used to guarantee the Lipschitz continuity of the Q-value functions, for a class of Lipschitz-valued policies. \n\n2. **Approximate TD error**: \n\n>*The approximate TD error in equation 6 makes sense to use as an approximate trust measure, but I'll caution that in practice the magnitude of these values can vary by orders of magnitude and is highly MDP dependent.*\n\nWe recognize that the magnitude of approximate TD error values can vary significantly across MDPs and models. Your point about the necessity of introducing MDP/model dependent scale/normalization hyperparameters makes a lot of sense from a practical perspective. \n\nOur results validate the existence of such hyper-parameters to guarantee the stated consistency and robustness tradeoff. We will supplement empirical results in the appendix to empirical address this issue. Exploring adaptive scaling methods or learning these hyper-parameters alongside the algorithm can be interesting future directions.\n\n3. **Applicability in Different Contexts**: \n\n>*\"Confident but wrong\" is a sadly common phenomenon in deep RL.*\n\nThank you for bringing up this point. Our theoretical analysis may shed some light on alleviating the \"confident but wrong\" phenomenon in deep RL. Indeed, it can be the case that a value-based policy generates low TD-error while having bad performance in practice. The choice of the estimated TD-error used in the definition of $R_t$ has an interesting decomposition shown in Lemma 4 (Appendix B.3). This lemma is further used in the robustness analysis in Appendix D to show that because of a telescoping property, when such an accumulated estimated TD-error is small, then the expected dynamic regret is also small, utilizing Theorem D.1. In practice, using such an accumulated estimated TD-error with the right hyper-parameter $\\beta$ can reflect the true performance of the value-based policy.\n\n>*I wonder if relative TD error (compared to some MDP-specific baseline or a running average or similar) might make more sense in practice for equation 6. It might be useful for future work to look at some of the literature on exploration and robust/safety-conscious RL and how uncertainty metrics are used in those fields.*\n\nIt would be very interesting to theoretically understand if the relative TD error can provide more benefits. We highly appreciate the suggestion of incorporating ideas from the exploration and robust/safety-conscious RL literature. Our current work is not dealing with hard constraints but we are looking forward to investigate how to use novelty/uncertainty metrics to address different tradeoffs and challenges. We understand that the current work might have limitations that are out of scope, but we are committed to addressing them in our future research. Once again, your expertise and perspective have been invaluable, and we remain open to further feedback.\n\n[Hinderer et al.] Hinderer, Karl. \"Lipschitz continuity of value functions in Markovian decision processes.\" Mathematical Methods of Operations Research 62 (2005): 3-22.\n\n[Asadi et al.] Asadi, Kavosh, Dipendra Misra, and Michael Littman. \"Lipschitz continuity in model-based reinforcement learning.\" International Conference on Machine Learning. PMLR, 2018.\n\n[Gelada et al.] Gelada, Carles, et al. \"Deepmdp: Learning continuous latent space models for representation learning.\" International Conference on Machine Learning. PMLR, 2019.\n\n[Tang et al.] Tang, Ziyang, et al. \"Off-policy interval estimation with lipschitz value iteration.\" Advances in Neural Information Processing Systems 33 (2020): 7887-7897.\n\n[Kim et al.] Kim, Jeongho, and Insoon Yang. \"Hamilton-Jacobi-Bellman equations for Q-learning in continuous time.\" Learning for Dynamics and Control. PMLR, 2020."}, {"review_id": "P206DCXWiu", "reviewer": "Reviewer_SGod", "summary": "The paper proposes a novel algorithm that combines a robust policy and a potentially untrusted machine learning based policy. The idea is to be able to achieve a trade-off between robustness and consistency or high performance entailed by the ML policy. The paper suggests a novel projection algorithm along with theoretical guarantees on the proposed algorithm.", "questions": "#### === *Motivation* ===\n\nChecking my understanding of the problem at hand, we have a default robust policy $\\bar{\\pi}$ as well as a ML based policy $\\tilde{\\pi}$ whose performance guarantee is potentially not trusted. The aim is to derive a new policy that combines the two and be able to achieve consistency vs. robustness trade-off in real-time decision making, does this sound right?\n\nI'd suggest giving more concrete examples for this setup, e.g. education, medical and so on, such that it is better to contextualize the problem at hand and better understand various algorithmic components.\n\n#### === *Fig 1* ===\n\nRightmost plot of Fig 1 -- what's on the x-axis and y-axis? There should be more explanations in the caption.\n\n#### === *Projection pursuit* ===\n\nThe projection pursuit policy derived in Sec 4 seems to be the core contribution of the paper and proposes to combine the two policies using a projection step. A main criticism might be that the algorithm seems specialized to continuous action, where the projection is more well defined? What if the action space is discrete, do we carry out projection in the logits / probability space or in the discrete action space?\n\n#### === *Empirical assessment* ===\n\nThere is no empirical assessment of the approach at all in the paper, as the narrative is purely theoretical. Though the theoretical contribution of the paper seems solid, readers from the NeurIPS community would certainly benefit from certain empirical validations of the theoretical insights in the paper. One should at least test the e.g. projection pursuit algorithm in some even potentially artificial domains, or even real domains (simulated envs) and showcase how the bound prediction is reflected in practice. One would also benefit from a discussion on how those hyper-parameters (e.g. regret budget $R_t$) would actually impact algorithm performance in practice.", "limitations": "Discussed above.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper seems to have solid theoretical grounding on the proposed algorithm, the background problem is also relatively well motivated and can be useful for general contexts where a ML policy is present alongside a default robust policy. This can be of interest to the general decision making practitioners for real applications.", "weaknesses": "The paper can be potentially improved by being more concrete about the problems and applications it aims to address, as well as showcasing some empirical evidence that the suggested algorithm achieves nice guarantees predicted by the theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and insightful comments. Below are our responses to your specific comments and questions:\n\n1. **Motivation**: \n\n>*The aim is to derive a new policy that combines the two and be able to achieve consistency vs. robustness trade-off in real-time decision making, does this sound right? I'd suggest giving more concrete examples for this setup.*\n\nYes, your description is correct. Indeed, the core objective of our work is to derive a new policy that effectively balances consistency and robustness in real-time decision-making scenarios. \n\nIn detail, our approach involves combining a default robust policy (denoted as $\\overline{\\pi}$) with a machine-learning-based policy (denoted as $\\widetilde{\\pi}$) whose performance guarantee may not be entirely trusted.  In addition, we would like to highlight that our main contribution is not only proposing such a model, but also characterizing how Q-value functions can help improve the consistency and robustness tradeoff, a.k.a the \"gray-box setting\" in the manuscript. We show that this gray-box feedback has nontrivial advantages in terms of the trade-off over simply combing a black-box policy with a robust baseline.\n\nWe agree with your suggestion of furnishing our models with more concrete examples to enhance the presentation. In the revised version, we will include real-world applications to better illustrate the practical relevance of our algorithm. For instance, a relevant example could be decision-making in power systems, where traditional methods as robust baselines *often exist*. In such scenarios, utilities companies may *hesitate to deploy* reinforcement learning algorithms for critical decision-making tasks, such as optimizing battery charging/discharging schedules or controlling inverters for voltage/frequency regulation.  Our provably efficient and robust policy provides a reliable solution for these applications. \n\nAnother quick example is to navigate a drone in a windy day. The drone relies on a pre-trained value-based policy and a baseline controller such as PID or MPC. By characterizing how Q-value advice can improve the consistency and robustness tradeoff, our results offer provable solutions to strike the right balance between the value-based policy and the baselines. In our revised paper, we will use these examples to motivate our problem and show how our methods can be applied in a wide range of applications where a Wasserstein robust baseline exists.\n\n2.  **Figure 1**: \n\nWe apologize for not explicitly defining $\\varepsilon$ and $\\mathsf{RoE}$ in Fig 1. The formal definitions of $\\varepsilon$ and $\\mathsf{RoE}$ are in Eq.(4) (line 239-240) and Definition 2 (line 146-148). We will improve the caption by expilcity pointing to the right places of the definitions.\n\n3. **Projection Pursuit**: \n\n>*What if the action space is discrete, do we carry out projection in the logits / probability space or in the discrete action space?*\n\nThank you for raising this important point! \n\nWe apologize for any confusion caused by the presentation in the manuscript. We have indeed provided a footnote on page 3, under line 138, briefly introducing how our model and methods can be generalized to discrete settings and leave the details in the appendix. We understand the importance of making this discussion more explicit in the main body of the paper. In the revised version, we will address this concern by providing a clearer and more detailed explanation.\n\nSpecifically, when the action space $\\mathcal{U}$ is discrete, we can define it as the set of all probability distributions on a finite action space, which forms a probability simplex that is convex and compact. To carry out the projection in the discrete action and state spaces, we can lift the norms from the original spaces to distributions on $\\mathcal{X}$ and $\\mathcal{U}$. This general norm can be used to define the Wasserstein robustness (Definition 3) in the discrete action space. Consider an MDP environment and denote by $\\Delta(\\mathcal{A})$ and $\\Delta(\\mathcal{S})$ the sets of probability distributions over $\\mathcal{A}$ and $\\mathcal{S}$. Given a policy $\\overline{\\pi}_t: \\mathcal{S} \\to \\Delta(\\mathcal{A})$ for $t \\in [T]$, let $\\{\\overline{P}_t\\}$ denote the lifted state transition probability that maps $\\mathcal{S}$ to $\\Delta(\\mathcal{S})$, defined as  $\\overline{P}_t(s; s') = \\sum_a\\overline{\\pi}_t(s; a){P}_t(s, a; s').$ We can find a Wasserstein robust baseline in the discrete setting. The key idea is to show that $\\overline{P}_t$ forms a contractive mapping with respect to the total variance distance (Lemma 1 in Appendix A.2.) and this contraction property is used to give the desired Wasserstein robustness. *A detailed discussion is in the supplementary material (Appendix A.2).* We will better clarify this in the main body of the revised paper.\n\n4. **Empirical Assessment**: \n\n> *There is no empirical assessment of the approach at all in the paper, as the narrative is purely theoretical. Though the theoretical contribution of the paper seems solid, readers from the NeurIPS community would certainly benefit from certain empirical validations of the theoretical insights in the paper.*\n\nWe appreciate your recognition of the solid theoretical contribution characterizing how Q-value functions can improve the consistency and robustness tradeoff in a general MDP model, which we believe is a first-of-its-kind result. \n\nWhile our main contribution lies in the theoretical side, we agree that empirical validation of our theoretical insights is essential to demonstrate the practical applicability and effectiveness of our approach. In the revised version of the paper, we will address this concern in the appendix by including empirical assessments of our approach. Furthermore, we will consider adding experiments to explore the impact of hyper-parameters, such as the tuning parameter $\\beta$ in practice. Thank you again for your constructive feedback!"}, {"review_id": "VfASvxHYvZ", "reviewer": "Reviewer_BJJd", "summary": "The authors study the tradeoff between consistency and robustness in the context of a single-trajectory time-varying Markov Decision Process (MDP) with untrusted machine-learned advice. Time-varying MDPs are relevant when dealing with environments where costs, rewards, and transition probabilities might change over time. In such settings, it is essential to design algorithms that can adapt to the changing dynamics of the environment. The proposed Projection Pursuit Policy (PROP) aims to balance the performance of an untrusted machine-learned policy with a trusted robust policy, taking into account the time-varying nature of the problem. The algorithm is designed to make better use of Q-value advice from the untrusted policy while maintaining worst-case performance guarantees close to those provided by the robust policy. The authors provide theoretical analysis for the consistency and robustness of the proposed algorithm. In the appendix, the authors also provide examples to demonstrate the versatility and effectiveness of their findings to various real-world problems.", "questions": "The authors mentioned in the abstract that their method can be applied in the discrete action space setting. However, the Projection Pursuit Policy may require adjustments to ensure that the resulting action remains feasible. When combining actions from different policies or projecting them onto a certain space, the resulting action may not lie exactly in the discrete action space. These adjustments may affect the theoretical guarantees of the algorithm, and further analysis might be needed to determine the impact of such modifications on the consistency and robustness tradeoffs of the Projection Pursuit Policy in the discrete action space setting.\n\nThe $\\epsilon$ parameter in Figure 1 is not introduced. It seems that it should be the same as in Equation 4. \n", "limitations": "The dependence of the theoretical results on the parameter $\\lambda$ in the black box setting may affect the practical implementation of the algorithm, as the choice of $\\lambda$ could influence the trade-off between consistency and robustness. Potential strategies for selecting an appropriate value are needed.\n\nIn the grey box setting, the theoretical results are only valid for some $\\beta$, which should satisfy the condition $R_t = 0$. It may be challenging to determine a suitable value of $\\beta$ in practice. Further analysis of the algorithm's performance and robustness under different values of $\\beta$ would be valuable.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Originality:\n\nThe paper presents a novel learning-augmented algorithm (PROP) for MDPs with Q-value predictions.\n\nThe work considers both black-box and grey-box settings, demonstrating the benefits of leveraging additional structural information in achieving improved performance guarantees.\n\nQuality:\n\nThe submission is technically sound, and the claims are well supported by theoretical analysis.\n\nThe authors provide a thorough analysis of the consistency and robustness tradeoffs in the context of MDPs.\n\n\nClarity:\n\nThe submission is clearly written and well-organized.\n\nSignificance:\n\nThe work advances the state of the art in learning-augmented algorithms for MDPs and demonstrates the potential benefits of utilizing value-based policies as advice.\n\nThe findings are relevant to researchers and practitioners interested in developing algorithms that can adapt to changing environments while maintaining performance guarantees.", "weaknesses": "Insufficient comparison to existing approaches: The paper does not provide a detailed comparison of the proposed PROP algorithm with existing learning-augmented algorithms, particularly in the context of discrete action spaces. A thorough comparison, both in terms of theoretical analysis and empirical evaluations, would help demonstrate the advantages and potential improvements offered by the proposed approach over existing methods. This would also provide a clearer understanding of the practical implications and the extent to which the proposed method advances the state of the art. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe sincerely appreciate your thoughtful feedback and valuable insights regarding our paper. Below we respond to your questions and concerns: \n\n1. **Comparison to Existing Approaches**:\n\n>*Insufficient comparison to existing approaches: The paper does not provide a detailed comparison of the proposed PROP algorithm with existing learning-augmented algorithms, particularly in the context of discrete action spaces.*\n\nWe acknowledge the importance of providing a more detailed comparison with existing learning-augmented algorithms. Our work stands as a novel contribution in the field as it represents the first-of-its-kind result in designing learning-augmented algorithms for general MDP models.\n\nExisting learning-augmented algorithms, as reviewed in the first part of Section 1.2, have mainly focused on specific models and online problems, such as ski rental, caching, bipartite matching, convex body chasing, online covering, etc. These approaches primarily revolve around black-box advice, making them more limited in their applicability to general MDP scenarios.\n\nIn the revised version of our paper, we will provide a more comprehensive analysis by comparing our proposed approach against relevant existing methods to clarify the distinctive advantages and contributions of our work in the context of learning-augmented algorithms. \n\n2. **Discrete Action Space Setting**: \n\n>*The authors mentioned in the abstract that their method can be applied in the discrete action space setting. However, the Projection Pursuit Policy may require adjustments to ensure that the resulting action remains feasible.*\n\nThank you for the insightful question and we truly appreciate your attention to the applicability of our method in the discrete action space setting. \n\nThe footnote on page 3, under line 138 briefly sketches the generalization of our model and methods to discrete settings. We acknowledge that our presentation may have appeared simplistic, and we apologize for any confusion caused. Let us elaborate how our the algorithm can be generalized. In the discrete setting, we can lift the norm definitions to distributions over $\\mathcal{X}$ and $\\mathcal{U}$, allowing us to define Wasserstein robustness effectively. Our results can be extended to this discrete setting as well. Specifically, when the action space $\\mathcal{U}$ is discrete, we can define it as the set of all probability distributions on a finite action space, which forms a probability simplex. This ensures that $\\mathcal{U}$ remains convex and compact, aligning with the requirements for our approach in the continuous action space setting to be applied. \n\nConsider an MDP environment with a finite state space $\\mathcal{S}$ and a finite action space $\\mathcal{A}$. Denote by $\\Delta(\\mathcal{A})$ and $\\Delta(\\mathcal{S})$ the sets of probability distributions over $\\mathcal{A}$ and $\\mathcal{S}$. Given a policy $\\overline{\\pi}_t: \\mathcal{S} \\to \\Delta(\\mathcal{A})$ for $t \\in [T]$, let $\\{\\overline{P}_t\\}$ denote the lifted state transition probability that maps $\\mathcal{S}$ to $\\Delta(\\mathcal{S})$, which is defined as \n$\\overline{P}_t(s; s') = \\sum_a\\overline{\\pi}_t(s; a){P}_t(s, a; s').$\nWe can find a Wasserstein robust baseline policy in this discrete setting. The key idea is to show that the one-step transition probability $\\overline{P}_t$ forms a contractive mapping with respect to the total variance distance (Lemma 1 in Appendix A.2.) and this contraction property can be used to establish the desired Wasserstein robustness.\n *A detailed discussion can be found in the submitted supplementary material (Appendix A.2).*  To address your concern, we will provide a more concrete and detailed explanation in the main body of the paper regarding the application of our approach in the discrete action space setting. Thank you again for your feedback!\n\n3. **Parameter in Figure 1**: \n\n>*The parameter $\\varepsilon$ in Figure 1 is not introduced. It seems that it should be the same as in Equation 4.*\n\nWe apologize for causing the confusion. It should be the same as in Equation 4. We will ensure consistency in notation throughout the paper and make the necessary corrections for clarity.\n\n4. **Practical Implementation and Parameter Selection**: \n\n>*The dependence of the theoretical results on the parameter $\\lambda$ in the black box setting may affect the practical implementation. Potential strategies are needed.*\n\nThank you for pointing out this limitation. In fact, we haven't focused too much on optimizing the choice of $\\lambda$ for the black-box procedure, since the black-box procedure serves more like a benchmark (as used in previous learning-augmented algorithms) to highlight the usefulness of the \"gray-box\" feedback (Q-values), which is proven to nontrivially outperform the black-box setting. Our main focus is the selection and analysis of the robustness budget $R_t$ (Equation 7) in the grey-box setting.\n\nBesides, our analysis on the black-box procedure can be applied to any choice of $\\lambda\\in [0,1]$, as stated in Theorem C.1. in the appendix. In our revised version, we will add more clarification based on your suggestion.\n\n\n5. **Characterize the Right Choice of $\\beta$ in the Grey-Box Setting**: \n\n>*In the grey box setting, the theoretical results are only valid for some $\\beta$. It may be challenging to determine a suitable value of in practice.*\n\nWe appreciate your point about the challenge of determining a suitable hyperparameter $\\beta$ of in the grey box setting. \n\nWe agree that determining $\\beta$ is of special theoretical interests, based on our current results, which validate the existence of such hyperparameters to guarantee the stated consistency and robustness tradeoff. \n\nIn our future work, we will conduct further analysis to explore the algorithm's performance and robustness under different values of $\\beta$ to offer valuable insights into the algorithm's behavior in practical scenarios.\n\nThank you again for your insightful feedback!"}, {"review_id": "4MWYqYhiio", "reviewer": "Reviewer_qteD", "summary": "This work considers the setting of using advice in Markov Decision Processes (MDPs). They consider the setting of using only action suggestions (termed black-box) or action and Q-values (grey-box) from a potentially erroneous advisor. They propose an algorithm that decides between the advice and a robust policy by projecting the advisor’s suggested action onto a ball centered around the robust policy’s action. Depending on the type of advisor, the radii of the projection ball can be static (black-box) or dynamically-chosen based on the estimated error of the Q-values (grey-box). The algorithm is analyzed along the axes of consistency (performance) and robustness, and it is shown that the grey-box setting can achieve much better consistency and robustness than the black-box setting.", "questions": "Minor/Typos:\n\n- Algorithm 1 box line 5 and 6 should be switched, since we don’t know all $x_t$ before taking the selected actions.\n\n- L302, instead of $\\tilde{\\pi}_t$ should be $\\tilde{u}_t$?\n", "limitations": "They have addressed some limitations, but some questions remain (See Weaknesses)", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is very well-written and clear. There is a lot of effort in explaining the setting, the definitions, and the approach which helps with readability and understanding. \n\nThe results are more general than prior works, which had similar results in the tabular setting (Golowich, 2021), however, I am also not an expert in this area. \n\nThe Projection Pursuit Policy (PROP) approach generalizes the black-box and grey-box settings nicely, and the results for the grey-box setting are promising for future work.\n", "weaknesses": "I think the paper overall could benefit from some empirical or practical demonstration of the setting, similar to what is presented in Appendix A, but with more focus on the applicability of the algorithm.  Ideally this would be in the main body but I understand that this is difficult given the page limit.  \n\nMy only concern is in the usefulness of the setting and some of its assumptions, which I explain below and hope the authors can comment on.\n\nAn example of a setting this could be used in: we have learned an optimal or close-to-optimal policy/value function but our environment is non-stationary and may have shifted since we learned this policy. We also have a baseline policy that is known to be robust in this environment. We then use PROP to take an action depending on how much to trust the robust vs the previously-learned policy. My concerns are:\n\n- The grey-box advice is in the form of Q-values: The choice of $(\\infty, \\epsilon)$-consistent policies is quite strong (defined in L243). In most realistic situations, we might only be able to guarantee the Q-function on certain data-dependent distributions. I think a more natural assumption would be to consider slowly-varying dynamics, for example where the change in $\\mathbb{P}_t$ is bounded under some norm. Could you comment on the limitations of this assumption?\n\n- Access to a robust policy: This was discussed for the case of discrete MDPs and LQR, however for the case of general MDPs, how can this policy be obtained? If the environment is time-varying, it might also affect the robustness guarantees of the policy.\n\n- This may be out-of-scope but a central assumption is that advice is provided at each step: advice might generally only be provided in some steps and not in others but the agent should still have the ability to learn the best policy in those situations.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your insightful comments! Below are our responses to your specific comments and questions:\n\n1. **Non-stationary Environment**:\n\nThan you so much for providing more insights and potential application domains of our methods. In fact,\nexisting algorithms for non-stationary RL primarily focus on adapting classic stationary RL algorithms through methods such as slicing windows [Gajane et al.] [Cheung et al.] [Fei et al.] [Chen el al.], periodic restarts [Touati et al.] [Mao et al.], kernel-based design [Domingues et al.], and black-box reduction (MALG) [Wei et al.]. However, these algorithms have dynamic regret bounds that deteriorate as the environment changes faster. \n\nNext, we address the detailed concerns on the usefulness of the setting and assumptions below. \n\n2. **$(\\infty,\\varepsilon)$-Consistent Policies**:\n\nThe assumption of $(\\infty,\\varepsilon)$-consistent policies is stronger than assuming the norm can be bounded under a specific distribution $\\rho$ for general $L_{p,\\rho}$ norms (as defined in (4), line 239-240). The reason we choose to present our main results, such as Theorem 5.1 assuming the machine-learned policy is $(\\infty,\\varepsilon)$-consistent is to simplify the statement, since the goal of defining a consistency error is to quantify how the Q-value advice is close to optimal Q-value functions as in the traditional consistency and robustness metrics (c.f. references [2,3,19,20] in the manuscript). \n\nIn fact, the only place where we need a stronger bound characterizing the Q-value error is the consistency analysis in the proof of Theorem C.1. (see line 734 in Appendix C.1), where we need to bound $\\mu_t=\\zeta_t^{V}-\\zeta_t^{Q}$, which is defined as the difference $\\widetilde{Q}_t (x_t,\\widetilde{u}_t)-Q_t^{\\star}(x_t,u_t^{\\star}) - (\\widetilde{Q}_t (x_t,u_t)-Q_t^{\\star} (x_t,u_t))$.\nIf we assume that the policy is $(p,\\rho,\\varepsilon)$-consistent  where $\\rho$ is the trajectory distribution generated by the policy in Algorithm 1 (PROP), then the result also holds.\n\nBesides, it is worth mentioning that Theorem 5.4 can be proved for the general consistency error defined in (4) as well, as in the consistency analysis in Appendix D.2, if $\\varepsilon(p,\\rho)=0$ for the distribution $\\rho$ that is the trajectory distribution generated by the policy in  Algorithm 1 (PROP)), it implies that both $\\mathbb{E}[\\zeta_t^{Q}]$ and $\\mathbb{E}[\\zeta_t^{V}]$ are zeros for any $t\\in [T]$. We will further clarify this in the revised paper. \n\n3. **Access to a Robust Policy and General MDPs**: \n\nWe appreciate the reviewer's concern about obtaining a robust policy for general MDPs. Our main focus is on the general setting, and we believe that by formulating and proving our theorems for this broader context, we can significantly extend the application domains of our proposed methods. While we discussed specific cases of discrete MDPs and LQR, our theoretical framework is applicable to a wide range of MDPs, making it more versatile and relevant to various real-world scenarios.  \n\nRegarding the concern about time-varying environments, we would like to clarify that our model is designed as a single-trajectory MDP. In this formulation, the transition probability $P_t$ can change over time, allowing for non-stationary MDPs. Despite that the MDP may be non-stationary, our results still hold for each episode (single-trajectory). This characteristic of our model and results ensures that the proposed approach remains applicable even in dynamic environments where the underlying dynamics may change over time.\n\nMoreover, we have provided examples of specific models with rich applications where robust policies do exist and can be constructed explicitly. These examples demonstrate the practical feasibility and relevance of our approach in settings where robust policies can be readily obtained.\n\n4. **Assumption of Advice at Each Step**:\n\nThank you for raising this interesting point! While our current work focuses on the assumption of advice at each step, we acknowledge the importance of exploring the new setting where advice is intermittently provided. We believe this is a valuable direction for future research, and we are more than willing to investigate and extend our approach to accommodate such scenarios.\n\n5. **Minor/Typos**: \n\nThank you so much for pointing out the typos in the Algorithm 1, line 5-6 and line 302! We have fixed the typos in the manuscript.\n\n**References**\n\n[Gajane et al.] Gajane, Pratik, Ronald Ortner, and Peter Auer. \"A sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions. 2018\n\n[Cheung et al.] Cheung, Wang Chi, David Simchi-Levi, and Ruihao Zhu. \"Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism.\" International Conference on Machine Learning. PMLR, 2020.\n\n[Fei et al.] Fei, Yingjie, et al. \"Dynamic regret of policy optimization in non-stationary environments.\" Advances in Neural Information Processing Systems 33 (2020): 6743-6754.\n\n[Chen et al.] Chen, Liyu, and Haipeng Luo. \"Near-optimal goal-oriented reinforcement learning in non-stationary environments.\" Advances in Neural Information Processing Systems 35 (2022): 33973-33984.\n\n[Touati et al.] Touati, Ahmed, and Pascal Vincent. \"Efficient learning in non-stationary linear markov decision processes.\" 2020\n\n[Mao et al.] Mao, Weichao, et al. \"Near-optimal model-free reinforcement learning in non-stationary episodic mdps.\" International Conference on Machine Learning. PMLR, 2021.\n\n[Domingues et al.] Domingues, Omar Darwiche, et al. \"A kernel-based approach to non-stationary reinforcement learning in metric spaces.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\n[Wei et al.] Wei, Chen-Yu, and Haipeng Luo. \"Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach.\" Conference on learning theory. PMLR, 2021."}]

Author rebuttal:

Meta-review: The paper focuses on the important problem of online tuning of the consistency-robustness trade-off.
Some motivation of the proposed setting should be added, and the paper lacks empirical verification.
However, the theoretical contribution is reckoned to be significant, with many reviewers solidly recommending acceptance.
Decision: Accept (poster)