Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions

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.

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. The 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. The 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.

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. My 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. An 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: - 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? - 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. - 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.

Questions

Minor/Typos: - Algorithm 1 box line 5 and 6 should be switched, since we don’t know all $x_t$ before taking the selected actions. - L302, instead of $\tilde{\pi}_t$ should be $\tilde{u}_t$?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

They have addressed some limitations, but some questions remain (See Weaknesses)

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.

Strengths

Originality: The paper presents a novel learning-augmented algorithm (PROP) for MDPs with Q-value predictions. The work considers both black-box and grey-box settings, demonstrating the benefits of leveraging additional structural information in achieving improved performance guarantees. Quality: The submission is technically sound, and the claims are well supported by theoretical analysis. The authors provide a thorough analysis of the consistency and robustness tradeoffs in the context of MDPs. Clarity: The submission is clearly written and well-organized. Significance: The 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. The 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.

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. The $\epsilon$ parameter in Figure 1 is not introduced. It seems that it should be the same as in Equation 4.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

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. In 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.

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.

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.

Questions

#### === *Motivation* === Checking 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? I'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. #### === *Fig 1* === Rightmost plot of Fig 1 -- what's on the x-axis and y-axis? There should be more explanations in the caption. #### === *Projection pursuit* === The 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? #### === *Empirical assessment* === 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. 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.

Rating

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

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Discussed above.

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.

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). All 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. In 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. Despite 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. I'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. 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, 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. Another 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. Overall 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.

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. Regarding 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.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

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). I 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.

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. I 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.

Strengths

- The paper studies an interesting and salient problem and provides theoretical derivations for their findings. - The paper is clearly structured. - Limitations and broader impact are adequately studied. - 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. - Some decision choices (see Questions) require further discussion. - This paper is at times hard to follow and could be written in a more clear way.

Questions

- L 308: What is the impact of this approximation? - L 283: Could you give a practical example of the impact of this radii?

Rating

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

Confidence

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

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Limitations and the broader impact of this method are properly addressed.

Summary

Authors study algorithms for Marcov Decision Processes receiving advice in the form of a value-based machine-learned policy. Value-based policies decide their actions based on minimizing an estimated Q-function, which predicts the best possible outcome in the rest of the time horizon given a current action. Such policies are known to perform well in some practical scenarios, but collapse in others. They propose algorithms for two regimes. In the first regime, the algorithm receives only the action taken by the value-based policy while, in the second regime, it also receives an estimate of the Q-function used by the value-based policy to determine its action. In the first regime, they propose a consistency-robustness tradeoff. In the second regime, they use the additional information (Q-function) to estimate the quality of the advice provided by the value-based policy and tune the trade-off parameter online, obtaining consistency 1 and near-optimal robustness. They show that the analysis of their algorithm for the first regime is tight.

Strengths

* work on an important problem * online tuning of the consistency-robustness trade-off * 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. * requires machine-learned advice in a form of a value-based policies. Other kinds of policies might be also beneficial.

Questions

* In algorithm 1, should line 6 be part of the for loop?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

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.

Response to Rebuttal

Glad my comments were useful! I'm glad to hear of your interest in developing this topic further- I think this is a good foundation that could be high-impact with further development and the resolution of practical details in future work. I appreciate your comments on feasibility, I agree these issues (and others that I can't anticipate offhand) should be surmountable, although I expect that to be enough of a project to be worth a paper in its own right. The broader topic of trust metrics (for various ends) is a complex but important one in deep RL IMO. A little further afield from this work, policy-gradient trust methods like Proximal Policy Optimization and Trust Region Policy Optimization constrain gradient updates based on how far they deviate from a prior policy, and have become widespread on-policy policy gradient method baselines and might spark inspiration if you aren't familiar with that literature. As a casual thought, since prediction error/trust/etc metrics are often useful for computing gradient updates, I wonder if there is some theoretical connection between the quality of a given metric for gradient updates and its quality for this sort of gray-box learning-augmented approach? At the very least computed TD-error variance and sampling bias both reduce gray-box trust and produce worse/slower-to-converge gradients. As an outsider to the topic, I could see that connection being relevant for online training of learning-augmented algorithms, where a policy is trusted very little initially and given more influence as training progresses.

Response to rebuttal

Thank you for your detailed response! The practical examples provided by the authors are very insightful. I am more positive about this submission after the rebuttal and the excellent analyses done by my fellow reviewers. I strongly encourage the authors to include, as promised, the empirical validation on the supplementary material.

Thanks for the rebuttal

Thank you for the rebuttal. I hope the authors will indeed include empirical assessment in the final revision of the paper, as this can be very valuable to the readers in general. I'd raise my rating to weak accept.