Blackwell Online Learning for Markov Decision Processes

• URL: http://arxiv.org/abs/2012.14043v1
• Date: Mon, 28 Dec 2020 00:40:01 GMT
• Title: Blackwell Online Learning for Markov Decision Processes
• Abstract summary: This work provides a novel interpretation of Markov Decision Processes (MDP) from the online optimization viewpoint. We construct a Blackwell game induced by MDP, which bridges the gap among regret minimization, Blackwell approachability theory, and learning theory for MDP.
• Score: 28.79413432611949
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work provides a novel interpretation of Markov Decision Processes (MDP) from the online optimization viewpoint. In such an online optimization context, the policy of the MDP is viewed as the decision variable while the corresponding value function is treated as payoff feedback from the environment. Based on this interpretation, we construct a Blackwell game induced by MDP, which bridges the gap among regret minimization, Blackwell approachability theory, and learning theory for MDP. Specifically, from the approachability theory, we propose 1) Blackwell value iteration for offline planning and 2) Blackwell $Q-$learning for online learning in MDP, both of which are shown to converge to the optimal solution. Our theoretical guarantees are corroborated by numerical experiments.

Related papers

• Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback [59.287761696290865]
  We propose a computationally efficient algorithm that achieves a sublinear regret guarantee for contextual episodic Markov Decision Processes (MDPs) with personalized feedback.<n>We demonstrate the effectiveness of our method in learning personalized objectives from multi-turn interactions through experiments on both a synthetic episodic MDP and a real-world user booking dataset.
  arXiv  Detail & Related papers  (2026-02-09T06:29:54Z)
• Scalable Policy-Based RL Algorithms for POMDPs [6.2229686397601585]
  We consider an approach that solves a Partially Observable Reinforcement Learning (PORL) problem by approximating a POMDP model into a finite-state Markov Decision Process (MDP)<n>We show that the approximation error decreases exponentially with the length of this history.<n>To the best of our knowledge, our finite-time bounds are the first to explicitly quantify the error introduced when applying standard TD learning to a setting where the true dynamics are not Markovian.
  arXiv  Detail & Related papers  (2025-10-08T00:33:38Z)
• Online MDP with Transition Prototypes: A Robust Adaptive Approach [8.556972018137147]
  We consider an online robust Markov Decision Process (MDP) where we have the information of finitely many prototypes of the underlying transition kernel. We propose an algorithm that efficiently identifies the true underlying transition kernel while guaranteeing the performance of the corresponding robust policy.
  arXiv  Detail & Related papers  (2024-12-18T17:19:55Z)
• A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes [13.466249082564213]
  We propose an optimistic variant of PPO for episodic adversarial linear MDPs with full-information feedback. Compared with existing policy-based algorithms, we achieve the state-of-the-art regret bound in both linear MDPs and adversarial linear MDPs with full information.
  arXiv  Detail & Related papers  (2023-05-15T17:55:24Z)
• Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor [13.544364903649196]
  We introduce the Blackwell discount factor for Decision Processes (MDPs) We show that when the discount factor is larger than the Blackwell discount factor $gamma_mathrmbw$, all discounted optimal policies become Blackwell- and average-optimal.
  arXiv  Detail & Related papers  (2023-01-31T19:11:17Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  It is common to address the curse of dimensionality in Markov decision processes (MDPs) by exploiting low-rank representations. We consider an alternative definition of linear MDPs that automatically ensures normalization while allowing efficient representation learning. We demonstrate superior performance over existing state-of-the-art model-based and model-free algorithms on several benchmarks.
  arXiv  Detail & Related papers  (2022-07-14T18:18:02Z)
• Bridging the gap between QP-based and MPC-based RL [1.90365714903665]
  We approximate the policy and value functions using an optimization problem, taking the form of Quadratic Programs (QPs) A generic unstructured QP offers high flexibility for learning, while a QP having the structure of an MPC scheme promotes the explainability of the resulting policy. We illustrate the workings of our proposed method with the resulting structure using a point-mass task.
  arXiv  Detail & Related papers  (2022-05-18T10:41:18Z)
• Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning [156.5667417159582]
  This paper proposes a novel model of sequential information design, namely the Markov persuasion processes (MPPs) Planning in MPPs faces the unique challenge in finding a signaling policy that is simultaneously persuasive to the myopic receivers and inducing the optimal long-term cumulative utilities of the sender. We design a provably efficient no-regret learning algorithm, the Optimism-Pessimism Principle for Persuasion Process (OP4), which features a novel combination of both optimism and pessimism principles.
  arXiv  Detail & Related papers  (2022-02-22T05:41:43Z)
• Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization [66.35750142827898]
  This paper presents the first systematic study on policy optimization methods for online CO problems. We show that online CO problems can be naturally formulated as latent Markov Decision Processes (LMDPs), and prove convergence bounds on natural policy gradient (NPG) Furthermore, our theory explains the benefit of curriculum learning: it can find a strong sampling policy and reduce the distribution shift.
  arXiv  Detail & Related papers  (2022-02-11T03:17:15Z)
• Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity [50.38337893712897]
  We introduce the Effective Planning Window (EPW) condition, a structural condition on MDPs that makes no linearity assumptions. We demonstrate that the EPW condition permits sample efficient RL, by providing an algorithm which provably solves MDPs satisfying this condition. We additionally show the necessity of conditions like EPW, by demonstrating that simple MDPs with slight nonlinearities cannot be solved sample efficiently.
  arXiv  Detail & Related papers  (2021-06-15T00:06:59Z)
• Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Problems by Reinforcement Learning [52.74071439183113]
  We study the predict-then-optimize framework in the context of sequential decision problems (formulated as MDPs) solved via reinforcement learning. Two significant computational challenges arise in applying decision-focused learning to MDPs.
  arXiv  Detail & Related papers  (2021-06-06T23:53:31Z)
• Exploration-Exploitation in Constrained MDPs [79.23623305214275]
  We investigate the exploration-exploitation dilemma in Constrained Markov Decision Processes (CMDPs) While learning in an unknown CMDP, an agent should trade-off exploration to discover new information about the MDP. While the agent will eventually learn a good or optimal policy, we do not want the agent to violate the constraints too often during the learning process.
  arXiv  Detail & Related papers  (2020-03-04T17:03:56Z)

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.