Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision Processes

• URL: http://arxiv.org/abs/2405.02188v1
• Date: Fri, 3 May 2024 15:44:31 GMT
• Title: Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision Processes
• Authors: Sang Bin Moon, Abolfazl Hashemi,
• Abstract summary: We introduce and study a new variant of AMDP, which aims to minimize regret while utilizing a set of cost predictors. We develop a new policy search method that achieves a sublinear optimistic regret with high probability, that is a regret bound which gracefully degrades with the estimation power of the cost predictors.
• Score: 5.116582735311639
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Adversarial Markov Decision Process (AMDP) is a learning framework that deals with unknown and varying tasks in decision-making applications like robotics and recommendation systems. A major limitation of the AMDP formalism, however, is pessimistic regret analysis results in the sense that although the cost function can change from one episode to the next, the evolution in many settings is not adversarial. To address this, we introduce and study a new variant of AMDP, which aims to minimize regret while utilizing a set of cost predictors. For this setting, we develop a new policy search method that achieves a sublinear optimistic regret with high probability, that is a regret bound which gracefully degrades with the estimation power of the cost predictors. Establishing such optimistic regret bounds is nontrivial given that (i) as we demonstrate, the existing importance-weighted cost estimators cannot establish optimistic bounds, and (ii) the feedback model of AMDP is different (and more realistic) than the existing optimistic online learning works. Our result, in particular, hinges upon developing a novel optimistically biased cost estimator that leverages cost predictors and enables a high-probability regret analysis without imposing restrictive assumptions. We further discuss practical extensions of the proposed scheme and demonstrate its efficacy numerically.

Related papers

• Uncertainty-Penalized Direct Preference Optimization [52.387088396044206]
  We develop a pessimistic framework for DPO by introducing preference uncertainty penalization schemes. The penalization serves as a correction to the loss which attenuates the loss gradient for uncertain samples. We show improved overall performance compared to vanilla DPO, as well as better completions on prompts from high-uncertainty chosen/rejected responses.
  arXiv  Detail & Related papers  (2024-10-26T14:24:37Z)
• Learning-Augmented Robust Algorithmic Recourse [7.217269034256654]
  Algorithmic recourse provides suggestions of minimum-cost improvements to achieve a desirable outcome in the future. Machine learning models often get updated over time and this can cause a recourse to become invalid. We propose a novel algorithm for this problem, study the robustness-consistency trade-off, and analyze how prediction accuracy affects performance.
  arXiv  Detail & Related papers  (2024-10-02T14:15:32Z)
• Asymptotically Optimal Regret for Black-Box Predict-then-Optimize [7.412445894287709]
  We study new black-box predict-then-optimize problems that lack special structure and where we only observe the reward from the action taken. We present a novel loss function, which we call Empirical Soft Regret (ESR), designed to significantly improve reward when used in training. We also show our approach significantly outperforms state-of-the-art algorithms on real-world decision-making problems in news recommendation and personalized healthcare.
  arXiv  Detail & Related papers  (2024-06-12T04:46:23Z)
• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  The Predict-Then-Forecast (PtO) paradigm in machine learning aims to maximize downstream decision quality. This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives. It shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
  arXiv  Detail & Related papers  (2024-02-12T16:33:35Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• Robust Losses for Decision-Focused Learning [2.9652474178611405]
  Decision-focused learning aims at training the predictive model to minimize regret by making a suboptimal decision. empirical regret can be an ineffective surrogate because empirical optimal decisions can vary substantially from expected optimal decisions. We propose three novel loss functions that approximate expected regret more robustly.
  arXiv  Detail & Related papers  (2023-10-06T15:45:10Z)
• A Note on Task-Aware Loss via Reweighing Prediction Loss by Decision-Regret [11.57423546614283]
  We propose a decision-aware version of predict-then-optimize. We reweigh the prediction error by the decision regret incurred by an (unweighted) pilot estimator of costs. We show that this approach can lead to improvements over a "predict-then-optimize" framework.
  arXiv  Detail & Related papers  (2022-11-09T18:59:35Z)
• Policy Gradient Bayesian Robust Optimization for Imitation Learning [49.881386773269746]
  We derive a novel policy gradient-style robust optimization approach, PG-BROIL, to balance expected performance and risk. Results suggest PG-BROIL can produce a family of behaviors ranging from risk-neutral to risk-averse.
  arXiv  Detail & Related papers  (2021-06-11T16:49:15Z)
• A Regret Minimization Approach to Iterative Learning Control [61.37088759497583]
  We propose a new performance metric, planning regret, which replaces the standard uncertainty assumptions with worst case regret. We provide theoretical and empirical evidence that the proposed algorithm outperforms existing methods on several benchmarks.
  arXiv  Detail & Related papers  (2021-02-26T13:48:49Z)
• Reward Biased Maximum Likelihood Estimation for Reinforcement Learning [13.820705458648233]
  Reward-Biased Maximum Likelihood Estimate (RBMLE) for adaptive control of Markov chains was proposed. We show that it has a regret of $mathcalO( log T)$ over a time horizon of $T$ steps, similar to state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2020-11-16T06:09:56Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  We consider online learning for episodically constrained Markov decision processes (CMDPs) We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-02T05:02:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.