Introduction

Machine-learned predictions and hand-crafted algorithmic advice are both crucial in online decisionmaking problems, driving a growing interest in learning-augmented algorithms [1,2] that exploit the benefits of predictions to improve the performance for typical problem instances while bounding the worst-case performance [3,4]. To this point, the study of learning-augmented 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 advice/predictions is often available and can potentially improve the performance of learning-augmented algorithms.

A notable example that motivates our work is the problem of minimizing costs (or maximizing rewards) in a single-trajectory Markov Decision Process (MDP). More concretely, a value-based machine-learned policy e ⇡ can be queried to provide suggested actions as advice to the agent at each step [5][6][7]. Typically, the suggested actions are chosen to 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 Q-value function itself can also provide additional information (e.g., the long-term impact of choosing a certain action) potentially useful to the design of a learning-augmented algorithm. Thus, this leads to two different designs for learning-augmented algorithms in MDPs: black-box algorithms and grey-box algorithms. A learning-augmented algorithm using e ⇡ is black-box if e ⇡ provides only the suggested action e u to the learning-augmented algorithm, whereas it is value-based (a.k.a., grey-box) if e ⇡ provides an estimate of the Q-value function e Q (that also implicitly includes a suggested action e u obtained by minimizing e Q) to the learning-augmented algorithm.

Value-based policies e

⇡ 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 [8][9][10][11], policy collapse [12], sample inefficiency [13], and/or when training data is biased [14]. As a consequence, such policies often are referred to as "untrusted advice" in the literature on learning-augmented algorithms, where the notion of "untrusted" highlights the lack of performance guarantees. In contrast, recent studies in competitive online control [15][16][17][18][19][20][21] 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.e., ⇡ provides "trusted advice." Typically, the goal of a learning-augmented online algorithm [1,3] 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-learned policy e ⇡ and a robust policy ⇡ naturally leads to a 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:

Can Q-value advice from an untrusted machine-learned policy, e ⇡, in a grey-box scenario provide more benefits than the black-box action advice generated by e ⇡ in the context of consistency and robustness tradeoffs for MDPs?

Contributions

We answer the question above in the affirmative by presenting and analyzing a unified projectionbased learning-augmented online algorithm (PROjection Pursuit policy, simplified as PROP in Algorithm 1) that combines action feedback from a trusted, robust policy ⇡ with an untrusted ML policy e ⇡. 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 machinelearned advice can 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-ofits-kind learning-augmented algorithm that applies to general MDP models, which allow continuous 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 [3,22,23,4] for the competitive ratio. We show in Theorem 5.2 that for the black-box setting, PROP is (1 + O(( 1) ))-consistent and (ROB + O( ))-robust where 0   1 is a hyper-parameter. Moreover, for the black-box setting, PROP cannot be both (1 + o( ))-consistent and (ROB + o(( 1) ))-robust for any 0   1 where is the diameter of the action space. In sharp contrast, by using a careful design of a robustness budget parameter in PROP with Q-value advice (grey-box setting), PROP is 1-consistent and (ROB + o(1))-robust.

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 e ⇡ and ⇡ for any single-trajectory time-varying, and even possibly adversarial environments -if the value-based policy e ⇡ is near-optimal, then the worst-case RoE(PROP) can approach 1 as governed by a consistency parameter; otherwise, RoE(PROP) can be bounded by the ratio of expectations of ⇡ subject to an additive term o(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 a learning-augmented algorithm (PROP) in a general MDP model, under both standard black-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 policies applicable for PROP are provided in Table 1(Section 3.1).

Related Work

Learning-Augmented 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 "consistency" 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,23], caching [27][28][29], bipartite matching [30], online covering [31,32], convex body chasing [4], nonlinear quadratic control [33]. The prior studies on learning-enhanced algorithms have mainly focused on creating meta-strategies that combine online algorithms with black-box predictions, and typically require manual setting of a trust hyper-parameter to balance consistency and robustness. A more recent learning-augmented algorithm in [33] investigated the balance between competitiveness and stability in nonlinear control in a black-box setting. However, this work limits the robust policy to a linear quadratic regulator and does not provide a theoretical basis for the selection of the trust parameters. [34] generalized the black-box advice setting by considering distributional advice.

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 as advice, and shows that such information can be utilized to reduce regret in a 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 a linear control system are shown to be useful in achieving a near-optimal consistency and robustness tradeoff. The predictive optimization problem solved by MPC [35,36,16,37] can be regarded as a 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.

MDP with External Feedback. Feedback from external sources such as control baselines [38,39], visual explanations [40], and human experts [41][42][43] is often available in MDP. This external feedback can be beneficial for various purposes, such as ensuring safety [44], reducing variance [38], training human-like chatbots [41], and enhancing overall trustworthiness [45], among others. The use 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 Temporal-Difference method to tune a coefficient 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][47][48].

Problem Setting

We consider a finite-horizon, single-trajectory, time-varying MDP with T discrete time steps. The state space X is a subset of a normed vector space embedded with a norm k • k X . The actions are chosen from a convex and compact set U in a normed vector space characterized by some norm k • k U . Notably, U can represent either continuous actions or the probability distributions used when choosing actions from a finite set. 1 The diameter of the action space U is denoted by := max u2U kuk U . Denote [T ] := {0, . . . , T 1}. For each time step t 2 [T ], let P t : X ⇥ U ! P X be the transition probability, where P X is a set of probability measures on X . We consider time-varying costs c t : X ⇥ U ! R + , while rewards can be treated similarly by adding a negative sign. An initial state x 0 2 X is fixed. This MDP model is compactly represented by MDP(X , U , T, P, c).

The goal of a policy in this MDP setting is to minimize the total cost over all T steps. The policy agent has no access to the full MDP. At each time step t 2 [T ], only the incurred cost value c t (x t , u t ) and the next state x t+1 ⇠ P t (•|x t , u t ) are revealed to the agent after playing an action u t 2 U. We denote a policy by ⇡ = (⇡ t : t 2 [T ]) where each ⇡ t : X ! U chooses an action u t when observing x t at step t 2 [T ]. Note that our results can be generalized to the setting when ⇡ t is stochastic and outputs a probability distribution on U . Given MDP(X , U, 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:

where the randomness in E P,⇡ is from the transition dynamics P = (P t : t 2 [T ]) and the policy ⇡ = (⇡ t : t 2 [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 1 (Expected dynamic regret). Given MDP(X , U , T, P, c), the (expected) dynamic regret of a policy ⇡ = (⇡ t : t 2 [T ]) is defined as the difference between the expected cost induced by the policy ⇡, J(⇡) in (1), and the optimal expected cost J ? := inf ⇡ J(⇡), i.e., DR(⇡) := J(⇡) 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 [51,52] will be used as an alternative performance metric in our main results.

Definition 2 (Ratio of expectations). Given MDP(X , U , T, P, c), the ratio of expectations of a policy ⇡ = (⇡ t : t 2 [T ]) is defined as RoE(⇡) := J(⇡)/J ? where J(⇡) and J ? are the same as in Definition 1.

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 [53][54][55]. Note that our analysis can be readily adapted to general Hölder continuous costs with minimal modifications.

Assumption 1 (Lipschitz costs). For any time step t 2 [T ], the cost function c t :

x 2 X , and u 2 U. 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 a valued-based policy, e ⇡, in the context of MDP(X , U , T, P, c). In particular, we denote by ROB 1 a ratio of expectation bound of the robust policy ⇡ such that the worst case RoE(⇡)  ROB. In the learningaugmented algorithms literature, these two goals are referred to as consistency and robustness [3,1]. 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 as good as e ⇡ when e ⇡ performs well (e.g., when the instance is not adversarial). Learning-augmented algorithms seek to achieve consistency and robustness by combining ⇡ and e ⇡, as illustrated in Figure 1. 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 is nearly always the focus in the learningaugmented algorithm literature is black-box advice -only providing a suggested action e u t without additional information. In contrast, on top of the action e u t , grey-box advice can also reveal the internal state of the learning algorithm, e.g., the Q-value e Q t in our setting. This contrast is illustrated in Figure 1.

Consistency and Robustness in MDPs

Compared to black-box advice, grey-box advice has received much less attention in the literature, despite its potential to improve tradeoffs between consistency and robustness as recently shown in [34,17]. Nonetheless, the extra information on top of the suggested action in a grey-box setting potentially allows the learning-augmented algorithm to make a better-informed decision based on the advice, thus achieving a better tradeoff between consistency and robustness than otherwise possible.

In the remainder of this section, we discuss the robustness properties for the algorithms we consider in our learning-augmented framework (Section 3.1), and introduce the notions of consistency in our grey-box and black-box models in Section 3.2.

Locally Wasserstein-Robust Policies

We begin with constructing a novel notion of robustness for our learning-augmented framework based on the Wasserstein distance as follows. Denote the robust policy by ⇡ := (⇡ t : t 2 [T ]), where each ⇡ t maps a system state to a deterministic action (or a probability of actions in the stochastic setting). Denote by ⇢ t1:t2 (⇢) the joint distribution of the state-action pair (x t , u t ) 2 X ⇥ U at time t 2 2 [T ] when implementing the baselines ⇡ t1 , . . . , ⇡ t2 consecutively with an initial state-action distribution ⇢. We use k • k X ⇥U := k • k X + k • k U as the included norm for the product space X ⇥ U. Let W p (µ, ⌫) denote the Wasserstein p-distance between distributions µ and ⌫ whose support set is X ⇥ U:

where p 2 [1, 1) and J (µ, ⌫) denotes a set of all joint distributions J with a support set X ⇥ U that have marginals µ and ⌫. Next, we define a robustness condition for our learning-augmented framework. Definition 3 (r-locally p-Wasserstein robustness). A policy ⇡ = (⇡ t : t 2 [T ]) is r-locally p-Wasserstein-robust if for any 0  t 1  t 2 < T and any pair of state-action distributions ⇢, ⇢ 0 where the the p-Wasserstein distance between them is bounded by W p (⇢, ⇢ 0 )  r, for some radius r > 0, the following inequality holds:

for some function s : [T ] ! R + satisfying P t2[T ] s(t)  C s where C s > 0 is a constant. Our robustness definition is naturally more relaxed than the usual contraction property in the control/optimization literature [25,35] -if any two different state-action distributions converge exponentially with respect to the Wasserstein p-distance, then a policy ⇡ is r-locally p-Wasserstein-robust. This is illustrated in Figure 2. Note that, although the Wasserstein robustness in Definition 3 well captures a variety of distributional robustness metrics such as the total variation robustness defined on finite state/action spaces, it can also be further generalized to other metrics for probability distributions.

As shown in Appendix A (provided in the supplementary material), by establishing a connection between the Wasserstein distance and the total variation metric, any policy that induces a regular 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 Wasserstein-robustmess in Definition 3 includes a 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 3 to a state-action perturbation bound in terms of the `2-norm when implementing the policy ⇡ from different starting states [35,19].

The connections discussed above highlight the existence of several well-known robust policies that satisfy Definition 3. 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 A.1 for details). The model assumption below will be useful in our main results. Assumption 2. There exists a -locally p-Wasserstein-robust baseline control policy (Definition 3) ⇡ for some p 1, where is the diameter of the action space U .

Consistency and Robustness for RoE

In parallel with the notation of "consistency and robustness" in the existing literature on learningaugmented algorithms [3,1], we define a new metric of consistency and robustness in terms of RoE. To do so, we first introduce an optimal policy ⇡ ? . Based on MDP(X , U , T, P, c), let ⇡ ? t = (⇡ ? t : t 2 [T ]) denote the optimal policy at each time step t 2 [T ], whose optimal Q-value function is

where E P,⇡ denotes an expectation with respect to the randomness of the trajectory {(x t , u t ) : t 2

[T ]} obtained by following a policy ⇡ and the transition probability P at each step t 2 [T ]. The Bellman optimality equations can then be expressed as

where we write

This indicates that for each time step t 2 [T ], ⇡ ? t is the greedy policy with respect to its optimal Q-value functions (Q ? t : t 2 [T ]). Note that for any t 2 [T ], Q ? t (x, u) = 0. Given this setup, the value-based policies e ⇡ := (e ⇡ t : t 2 [T ]) take the following form. For any t 2 [T ], a value-based policy e ⇡ t : X ! U produces an action e u t 2 arg min v2U e Q t (x t , v) by minimizing an estimate of the optimal Q-value function e Q t .

We make the following assumption on the machine-learned untrusted policy e ⇡ and the Q-value advice.

Assumption 3. The machine-learned untrusted policy e ⇡ is value-based. The Q-value advice e

We can now define a consistency measure for Q-value advice e Q t , which measures the error of the estimates of the Q-value functions due to approximation error and time-varying environments, etc. Let p 2 (0, 1]. Fix a sequence of distributions ⇢ = (⇢ t : t 2 [T ]) whose support set is X ⇥ U and let t be the marginal distribution of ⇢ t on X . We define a quantity representing the error of the Q-value advice

where

A policy with Q-value functions {Q t : t 2 [T ]} is said to be (", p, ⇢)-consistent if there exists an " satisfying (4). In addition, a policy is (0, 1)-consistent if e Q t is a Lebesgue-measurable function for all t 2 [T ] and (1, ")-consistent if the L 1 -norm satisfies

The consistency error of a policy in (4) quantifies how the Q-value advice is close to optimal Q-value functions. It depends on various factors such the function approximation error or training error due to the distribution shift, and has a close connection to a rich literature on value function approximation [57][58][59][60][61]. The results in [59] generalized the worstcase L 1 guarantees to arbitrary L p,⇢ -norms 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 as classification and regression, whose bounds are typically given on the expected error under some distribution. These results exemplify richer instances of the consistency definition (see ( 4)) and a summary of these bounds can be found in [61]. 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 learning-augmented algorithms [3,22,23,4]. We write the ratio of expectations RoE(") of a policy ⇡ as a function of the Q-value advice error " in terms of the L 1 norm, defined in (4).

Definition 4 (Consistency and Robustness

). An algorithm ⇡ is said to be k-consistent if its worst-case (with respect to the MDP model MDP(X , U, T, P, c)) ratio of expectations satisfies RoE(")  k for " = 0. On the other hand, it is l-robust if RoE(")  l for any " > 0.

The Projection Pursuit Policy (PROP)

In this section we introduce our proposed algorithm (Algorithm 1), which achieves near-optimal consistency while bounding the robustness by leveraging a robust baseline (Section 3.1) in combination with value-based advice (Section 3.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 a 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 t 2 [T ], we choose u t = Proj U t (e u t ) where a projection operator Proj U t (•) : U ! U is defined as

corresponding to the projection of u onto a ball U t := {u 2 U : ku ⇡ t (x t )k U  R t }. Note that when the optimal solution of ( 5) is not unique, we choose the one on the same line with ⇡ t (x t ) u.

The PROjection Pursuit policy, abbreviated as PROP, can be described as follows. For a time step t 2 [T ], let e ⇡ t : X ! U denote a policy that chooses an action e u t (arbitrarily choose one if there are multiple minimizers of e Q t ), given the current system state x t at time t 2 [T ] and step t 2 [T ]. An action u t = Proj U t (e u t (x t )) is selected by projecting the machine-learned action e u t (x t ) onto a norm ball U t defined by the robust policy ⇡ given a radius R t 0. Finally, PROP applies to both black-box and grey-box settings (which differ from each other in terms of how the radius R t is decided). The results under both settings are provided in Section 5, revealing a tradeoff between consistency and robustness.

The radii (R t : t 2 [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 e ⇡ -the larger budgets, the more trustworthiness and hence the more freedom for PROP to follow e ⇡. How the robustness budget is chosen differentiates the grey-box setting from the black-box one.

Algorithm 1 PROjection Pursuit Policy (PROP) Initialize :Untrusted policy e ⇡ = (e ⇡ t : t 2 [T ]) and baseline policy ⇡ = (⇡ t : t 2 [T ]) 1 for t = 0, . . . , T 1 do 2 //Implement black-box (Section 4.1) or grey-box (Section 4.2) procedures 3 (e u t , R t ) BLACK-BOX(x t ) or (e u t , R t ) GREY-BOX(x t ) 4 Set action u t = Proj U t (e u t ) where U t := {u 2 U : ku ⇡ t (x t )k U  R t } 5 Sample next state x t+1 ⇠ P t (•|x t , u t ) 6 end 4.1 Black-Box Setting

In the black-box setting, the only information provided by e ⇡ is a suggested action e u for the learningaugmented algorithm. Meanwhile, the robust policy ⇡ can also be queried to provide advice u. Thus, without additional information, a natural way to utilize both e ⇡ and ⇡ is to decide a projection radius at each time based on the how the obtained e u and u. More concretely, at each time t 2 [T ], the robustness budget R t is chosen by the following BLACK-BOX Procedure, where we set R t = ⌘ t with ⌘ t := ke u t u t k U representing the difference between the two advice measured in terms of the norm k • k U and 0   1 being a tradeoff hyper-parameter that measures the trustworthiness on the machine-learned advice. The choice of R t = ⌘ t can be explained as follows. The value of ⌘ t 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 a robust policy and an untrusted policy, by setting a larger , 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 hyper-parameter that can be pre-determined to yield a desired consistency and robustness tradeoff. The computation of R t is summarized in Procedure 1 below.

Procedure 1 BLACK-BOX Procedure at t 2 [T ] (Input: state x t and hyper-parameter 0   1) Implement e ⇡ t and ⇡ t to obtain e u t and u t , respectively. Set robustness budget R t = ⌘ t where ⌘ t := ke u t u t k U ; Return (e u t , R t )

Grey-Box Setting

In the grey-box setting, along with the suggested action e u, the value-based untrusted policy e ⇡ also provides an estimate of the Q-value function e Q that indicates the long-term cost impact of an action. To utilize such additional information informed by e Q t at each time t 2 [T ], we propose a novel algorithm that dynamically adjusts the budget R t to further improve the consistency and robustness tradeoff. More concretely, let us consider the Temporal-Difference (TD) error TD t = c t 1 + P t 1 e

V t e Q t 1 . Intuitively, if a non-zero TD-error is observed, the budget R t 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 : t 2 [T ]). To address this challenge, we use the following estimated TD-error based on previous trajectories: t (x t , x t 1 , u t 1 ) :=c t 1 (x t 1 , u t 1 ) + inf v2U e Q t (x t , v) e Q t 1 (x t 1 , u t 1 ) .

Denote by > 0 a hyper-parameter. Based on the estimated TD-error in (6), the robustness budget in Algorithm 1 is set as

which constitutes two terms. The first term ⌘ t := ke ⇡ t (x t ) ⇡ t (x t )k measures the decision discrepancy between the untrusted policy e ⇡ and the baseline policy ⇡, which normalizes the total budget, similar to the one used in the black-box setting in Procedure 1. The second term is the approximate TD-error, which is normalized by the Lipschitz constant L Q of Q-value functions. With these terms defined, the GREY-BOX Procedure below first chooses a suggested action e u t by minimizing e Q t and then decides a robustness budget R t using (7).

may not be fully trusted. On the other hand, this sharp contrast between the black-box and grey-box settings reveals that having access to 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 D. Applications of our main results are discussed in Appendix A.

Concluding Remarks

Our results contribute to the growing body of literature on learning-augmented 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, it is possible to achieve improved performance over a 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 is the lack of analysis of more general forms of black-box procedures. Understanding and quantifying the available structural information in a more systematic way is another future direction that could lead to advances in the design of learning-augmented online algorithms and their applications in various domains.