A Hierarchy of Policy Learning Problems

• URL: http://arxiv.org/abs/2607.03385v1
• Date: Fri, 03 Jul 2026 14:40:47 GMT
• Title: A Hierarchy of Policy Learning Problems
• Abstract summary: We provide a framework for studying the relationships between policy learning problems.<n>We show that the policy existence problem reduces to the improving policy problem.<n>These results highlight the value in studying a broader range of policy learning problems.
• Score: 25.912923963157752
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Policy learning has received substantial attention with the goal of learning policies from observational data for decision-making. A majority of work in this space has focused on developing algorithms for computing policies that minimize regret compared to the optimal policy. However, in many practical settings, there is insufficient data to obtain low regret. As a result, recent work has shifted attention to alternative objectives, most notably, studying whether it is possible to learn an improving policy that statistically significantly outperforms baseline policies. We argue that there is substantial merit in studying a broader range of policy learning problems. When there is insufficient data to learn an improving policy, there may still be useful questions that can be answered. To this end, we provide a mathematical framework for studying the relationships between policy learning problems. We formalize three problems within our framework: beyond the optimal policy problem and the improving policy problem, we also propose the policy existence problem, which aims to determine if an improving policy exists. Within our framework, we show that the policy existence problem reduces to the improving policy problem, which in turn reduces to the optimal policy problem; these reductions prove that each problem is at least as easy as the next one (in sample complexity). A key question remains: is this hardness strict? We provide partial answers. First, the gap between the optimal policy and improving policy problems is strict. For the improving policy and policy existence problems, we prove that a sublinear polynomial gap exists under natural conditions on improving policy learning algorithms. Thus, we may be able to answer questions about the existence of an improving policy even when we cannot find one. These results highlight the value in studying a broader range of policy learning problems.

Related papers

• Partial Policy Gradients for RL in LLMs [43.33467583837307]
  We propose a natural approach for modeling policy structure in policy gradients.<n>Smaller subsets represent simpler policies, which can be learned more reliably because their empirical gradient estimates are more accurate.<n>We evaluate the policies empirically on multiple persona-alignment conversational problems.
  arXiv  Detail & Related papers  (2026-03-06T10:47:41Z)
• Quantile-Optimal Policy Learning under Unmeasured Confounding [55.72891849926314]
  We study quantile-optimal policy learning where the goal is to find a policy whose reward distribution has the largest $alpha$-quantile for some $alpha in (0, 1)$.<n>Such a problem suffers from three main challenges: (i) nonlinearity of the quantile objective as a functional of the reward distribution, (ii) unobserved confounding issue, and (iii) insufficient coverage of the offline dataset.
  arXiv  Detail & Related papers  (2025-06-08T13:37:38Z)
• Residual Policy Gradient: A Reward View of KL-regularized Objective [48.39829592175419]
  Reinforcement Learning and Imitation Learning have achieved widespread success in many domains but remain constrained during real-world deployment.<n>Policy customization has been introduced, aiming to adapt a prior policy while preserving its inherent properties and meeting new task-specific requirements.<n>A principled approach to policy customization is Residual Q-Learning (RQL), which formulates the problem as a Markov Decision Process (MDP) and derives a family of value-based learning algorithms.<n>We introduce Residual Policy Gradient (RPG), which extends RQL to policy gradient methods, allowing policy customization in gradient-based RL settings.
  arXiv  Detail & Related papers  (2025-03-14T02:30:13Z)
• Conservative Exploration for Policy Optimization via Off-Policy Policy Evaluation [4.837737516460689]
  We study the problem of conservative exploration, where the learner must at least be able to guarantee its performance is at least as good as a baseline policy. We propose the first conservative provably efficient model-free algorithm for policy optimization in continuous finite-horizon problems.
  arXiv  Detail & Related papers  (2023-12-24T10:59:32Z)
• Residual Q-Learning: Offline and Online Policy Customization without Value [53.47311900133564]
  Imitation Learning (IL) is a widely used framework for learning imitative behavior from demonstrations. We formulate a new problem setting called policy customization. We propose a novel framework, Residual Q-learning, which can solve the formulated MDP by leveraging the prior policy.
  arXiv  Detail & Related papers  (2023-06-15T22:01:19Z)
• Towards A Unified Policy Abstraction Theory and Representation Learning Approach in Markov Decision Processes [39.94472154078338]
  We propose a unified policy abstraction theory, containing three types of policy abstraction associated to policy features at different levels. We then generalize them to three policy metrics that quantify the distance (i.e., similarity) of policies. For the empirical study, we investigate the efficacy of the proposed policy metrics and representations, in characterizing policy difference and conveying policy generalization respectively.
  arXiv  Detail & Related papers  (2022-09-16T03:41:50Z)
• CAMEO: Curiosity Augmented Metropolis for Exploratory Optimal Policies [62.39667564455059]
  We consider and study a distribution of optimal policies. In experimental simulations we show that CAMEO indeed obtains policies that all solve classic control problems. We further show that the different policies we sample present different risk profiles, corresponding to interesting practical applications in interpretability.
  arXiv  Detail & Related papers  (2022-05-19T09:48:56Z)
• PG3: Policy-Guided Planning for Generalized Policy Generation [25.418642034856365]
  We study generalized policy search-based methods with a focus on the score function used to guide the search over policies. The main idea behind our approach is that a candidate policy should be used to guide planning on training problems as a mechanism for evaluating that candidate. Empirical results in six domains confirm that PG3 learns generalized policies more efficiently and effectively than several baselines.
  arXiv  Detail & Related papers  (2022-04-21T21:59:25Z)
• Accelerating Safe Reinforcement Learning with Constraint-mismatched Policies [34.555500347840805]
  We consider the problem of reinforcement learning when provided with a baseline control policy and a set of constraints that the learner must satisfy. We propose an iterative policy optimization algorithm that alternates between maximizing expected return on the task, minimizing distance to the baseline policy, and projecting the policy onto the constraint-satisfying set. Our algorithm consistently outperforms several state-of-the-art baselines, achieving 10 times fewer constraint violations and 40% higher reward on average.
  arXiv  Detail & Related papers  (2020-06-20T20:20:47Z)
• Policy Evaluation Networks [50.53250641051648]
  We introduce a scalable, differentiable fingerprinting mechanism that retains essential policy information in a concise embedding. Our empirical results demonstrate that combining these three elements can produce policies that outperform those that generated the training data.
  arXiv  Detail & Related papers  (2020-02-26T23:00:27Z)
• Preventing Imitation Learning with Adversarial Policy Ensembles [79.81807680370677]
  Imitation learning can reproduce policies by observing experts, which poses a problem regarding policy privacy. How can we protect against external observers cloning our proprietary policies? We introduce a new reinforcement learning framework, where we train an ensemble of near-optimal policies.
  arXiv  Detail & Related papers  (2020-01-31T01:57:16Z)

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.