PaperlayerView exact revision on arXiv

Source-linked AI summary

Variational Policy Gradient Method for Reinforcement Learning with General Utilities

Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, Mengdi Wang

arXiv:2007.02151v1cs.LGstat.ML

TL;DR

General utility objectives in reinforcement learning can invalidate Bellman-based dynamic programming, motivating direct policy search over occupancy-measure functionals. The paper derives a variational policy-gradient method, estimates it from sample paths, and proves global convergence despite nonconvexity, with O(1/t) convergence generally and exponential convergence under hidden strong convexity.

  • Problem

    The paper addresses policy optimization for concave utility functions of state-action occupancy measures when general utilities invalidate the standard policy-gradient and dynamic-programming framework.

  • Method

    The paper derives a Variational Policy Gradient Theorem, formulates the gradient through a stochastic saddle-point problem, and estimates it using primal-dual stochastic approximation from policy-generated sample paths.

  • Results

    The variational policy-gradient scheme converges globally despite nonconvexity at O(1/t), with exponential convergence when the utility is strongly concave in occupancy measures.

  • Takeaways & Limitations

    The analysis extends policy-gradient convergence guarantees from cumulative-reward reinforcement learning to the broader class of concave occupancy-measure utilities.

  • Takeaways & Limitations

    The paper is purely theoretical and does not target a specific application; relationships between its optimality conditions and prior cumulative-reward conditions remain future work.

Abstract

from arXiv · show

In recent years, reinforcement learning (RL) systems with general goals beyond a cumulative sum of rewards have gained traction, such as in constrained problems, exploration, and acting upon prior experiences. In this paper, we consider policy optimization in Markov Decision Problems, where the objective is a general concave utility function of the state-action occupancy measure, which subsumes several of the aforementioned examples as special cases. Such generality invalidates the Bellman equation. As this means that dynamic programming no longer works, we focus on direct policy search. Analogously to the Policy Gradient Theorem \cite{sutton2000policy} available for RL with cumulative rewards, we derive a new Variational Policy Gradient Theorem for RL with general utilities, which establishes that the parametrized policy gradient may be obtained as the solution of a stochastic saddle point problem involving the Fenchel dual of the utility function. We develop a variational Monte Carlo gradient estimation algorithm to compute the policy gradient based on sample paths. We prove that the variational policy gradient scheme converges globally to the optimal policy for the general objective, though the optimization problem is nonconvex. We also establish its rate of convergence of the order $O(1/t)$ by exploiting the hidden convexity of the problem, and proves that it converges exponentially when the problem admits hidden strong convexity. Our analysis applies to the standard RL problem with cumulative rewards as a special case, in which case our result improves the available convergence rate.

1. Introduction

The paper asks whether direct policy search remains viable when general utility objectives invalidate Bellman-based dynamic programming, and answers positively with variational policy-gradient theory and convergence guarantees.

  • Motivation: General utilities extend cumulative rewards to concave functionals of state-action occupancy measures, covering constrained, exploratory, and imitation objectives.Cumulative reward is the linear special case.
  • Motivation: Without reward additivity, the problem becomes non-Markovian in the cost-to-go, so the Bellman equation, dynamic programming, and value-function methods fail.The action-value function is also not well-defined in this setting.
  • Scope: The paper focuses on direct policy search because standard policy-gradient methods lack their usual theorem and action-value function for general utilities.The work is theoretical and does not target a specific application.
  • Contributions: The Variational Policy Gradient Theorem formulates the parametrized policy gradient as the solution of a stochastic saddle-point problem.This provides a policy-gradient analogue for general utilities.
  • Contributions: O(1/√n) random estimation error is achieved using primal-dual stochastic approximation on sample paths from the current policy.Here n is the number of episodes, and the bound depends on utility properties.
  • Contributions: O(1/t) convergence to the global optimal policy follows despite nonconvexity, while strongly concave utilities yield exponential convergence.For cumulative rewards, the result improves the cited tabular policy-gradient rate; the analysis also matches rates of cited algorithmic variants.

2. Problem Formulation

The problem formulation maximizes a concave functional of a policy’s discounted state-action occupancy measure in a finite MDP, with cumulative reward as a special case.

  • MDP formulation: The MDP has finite state and action spaces, an initial state distribution, transition probabilities, and stationary policies mapping states to action distributions.The policy prescribes actions based on previous states.
  • General objective: The general objective optimizes a concave functional F of the cumulative discounted state-action occupancy measure λπ.The formulation is designed for objectives beyond cumulative rewards.
  • Occupancy formulation: The occupancy-measure formulation imposes flow constraints requiring λ to correspond to a policy, from which a policy can be extracted through a mapping Π.This gives an equivalent optimization problem in occupancy measures.
  • Special case: When F(λ) = ⟨r, λ⟩, the general problem reduces to the standard cumulative-reward MDP and its dual linear-program formulation.Thus the standard MDP is contained as a linear special case.
  • Examples: The framework includes constrained MDPs, exploration through entropy or feature covariance, and imitation through divergence from a prior state-visitation distribution.Examples include log-barrier penalties, entropy, KL divergence, Wasserstein distance, total variation, and Hellinger distance.
  • Examples: The formulation also supports feature-coverage objectives and multiple convex distances for matching demonstrations, before shifting to algorithm design.These examples motivate safety, exploration, and imitation objectives.

3. Variational Policy Gradient Theorem

The paper replaces the unavailable standard policy-gradient route for general utilities with a Fenchel-dual stochastic saddle-point formulation and sample-based estimation. It establishes conditions under which this variational gradient can be estimated efficiently.

  • Policy parameterization: Policy parameterization reduces optimization from the high-dimensional tabular policy space to a d-dimensional parameter space.The policy is represented as π = πθ with θ ∈ Θ ⊂ R^d.
  • Motivation: The standard policy-gradient theorem fails for general utilities because non-additive rewards eliminate the structure underlying its derivation.The paper instead defines the general-utility gradient through the occupancy measure and its utility function.
  • Variational policy gradient: The variational policy gradient is obtained by solving a stochastic saddle-point problem involving the Fenchel dual of the concave utility.Under concavity and continuous differentiability of F, Theorem 3.1 characterizes the steepest policy-ascent direction through this formulation.
  • Gradient construction: The resulting gradient combines a cumulative return, its vanilla policy gradient, and the gradient of the Fenchel dual.These components yield a valid policy gradient for general objectives.
  • Monte Carlo estimation: Monte Carlo estimates use sampled trajectories, with truncation error of order γ^K/(1 − γ) for length-K episodes.A sample-average approximation and a Monte Carlo stochastic-approximation scheme are provided.
  • Estimation guarantees: O(1/√n) error is suggested for finite-data variational policy-gradient estimation, with the bound depending on properties of F rather than the dimension of z.The analysis assumes boundedness and smoothness conditions on F and regularity of the policy parameterization; cumulative rewards are included as a special case.

4. Global Convergence of Policy Gradient Ascent

The policy-gradient objective is nonconvex in policy parameters, but hidden convexity in occupancy-measure space yields global optimality and O(1/t) convergence under stated regularity conditions. Strong concavity further gives exponential convergence, including improved guarantees for cumulative rewards.

  • Policy-gradient iteration: The policy-gradient scheme optimizes the objective by projected gradient ascent over policy parameters.The analysis studies maxθ∈Θ R(πθ) and uses Euclidean projection onto Θ.
  • Hidden convexity: Hidden convexity arises because the occupancy-measure mapping can be bijective while the objective is concave in occupancy measures.The result separates convex and nonconvex mappings and relies on regularity of the parameterization and its inverse.
  • Global optimality: Every first-order stationary point is globally optimal when the stated bijection, smoothness, and concavity conditions hold.Theorem 4.2 assumes Assumption 4.1 and a concave continuous utility extension around the feasible occupancy-measure set.
  • Convergence rates: O(1/t) convergence holds for general utilities under Lipschitz-gradient assumptions, despite nonconvexity in policy parameters.The guarantee exploits convex structure in occupancy-measure space rather than ordinary nonconvex stationary-point analysis.
  • Convergence rates: Strong concavity of the utility yields exponential convergence, with Kullback-Leibler-divergence regularization given as an example.The paper notes that such regularization can make policy search faster than the cumulative-return case.
  • Cumulative rewards: For cumulative rewards, the analysis improves the tabular policy-gradient iteration complexity from O(1/ϵ^2) to O(1/ϵ).The paper attributes the improvement to the hidden convexity exploited by the analysis and compares it with existing tabular policy-gradient results.

5. Experiments

Experiments on Frozen Lake evaluate gradient estimation, maximum-entropy exploration, and obstacle avoidance. The proposed methods produce accurate gradient estimates, broader state coverage under entropy maximization, and tunable reward-cost trade-offs under logarithmic barriers.

  • Experimental setup: The experiments use OpenAI Frozen Lake to numerically validate the proposed methods and theory.Additional experimental details are deferred to Appendix C.
  • Policy-gradient estimation: Algorithm 1’s gradient estimates converge to cosine similarity near 1 with the ground-truth gradient as samples increase.Figure 1 compares these estimates across general-utility instances with REINFORCE estimates for cumulative returns.
  • Maximum-entropy exploration: Maximum-entropy policy-gradient training achieves better state-space coverage than a uniformly random policy.The figure compares entropy over training and visualizes the world model, uniform occupancy, Fenchel-dual pseudo-reward, and learned occupancy.
  • Obstacle avoidance: Logarithmic-barrier policies concentrate occupancy away from costly obstacle states compared with cumulative-return REINFORCE.Figure 3 contrasts the barrier solution with the cumulative-return occupancy measure in the augmented Frozen Lake environment.
  • Obstacle avoidance: β = 0 achieves the highest reward but highest cost, whereas β = 4 achieves the lowest cost and lowest reward.Intermediate penalty settings β = 1 and β = 2 are also evaluated during training.

6. Broader Impact

The work is foundational and theoretical, without a specific application or basis for predicting broader impacts beyond speculation.

  • The paper is purely theoretical and does not target a specific application.
  • The authors state that potential positive and negative broader impacts cannot be assessed beyond speculation.

Supplementary Material for “Variational Policy Gradient Method for Reinforcement Learning with General Utilities”

The supplementary material details model-free variational policy-gradient estimation, special utility cases, and empirical comparisons in Frozen Lake.

  • Method: The Monte Carlo estimator alternates stochastic primal and dual updates using episodes generated by the current policy.
  • Special cases: The linear utility case recovers the standard policy gradient theorem for risk-neutral Markov decision processes.
  • Special cases: For constrained MDPs with a logarithmic barrier, estimating the gradient requires two policy gradients and accumulated reward.
  • Experiments: The Frozen Lake experiments use a softmax policy with 16 states and 4 actions, comparing variational estimates against a REINFORCE-based benchmark.

C.4 Details about the Constrained Markov Decision Process

The constrained Frozen Lake experiment compares unconstrained return optimization with logarithmic-barrier policies that trade reward for lower obstacle costs.

  • The experiment compares standard cumulative-return optimization with logarithmic barriers for avoiding costly states.
  • Constraint imposition concentrates policy probability away from obstacles and along paths from the start to the goal.
  • β = 0 achieves the highest reward but incurs the most costs, while β = 4 incurs lower cost and lower reward.
  • Training runs for 10K episode steps, evaluates test trajectories, and reports averages over the last 20 episodes using η = 0.1.

Appendix D. Proof of Theorem 3.1

The proof establishes boundedness and asymptotic equivalence of constrained saddle-point solutions, then decomposes estimation error into primal, dual, and limiting components.

  • The proof introduces bounded auxiliary constraint sets for the dual variable and shows these constraints become inactive for sufficiently small δ.
  • The proof uses Fenchel duality and first-order stationarity to connect the saddle-point formulation with the variational policy gradient.
  • The primal solution remains bounded, making the auxiliary constraint on x inactive and removable for sufficiently small δ.
  • Estimation error is decomposed through differences between exact and empirical primal-dual solutions, followed by the limit δ → 0.
  • Linearity of Q, V, and ∇θV in the reward function supports the proof's bounds on value and gradient estimators.

E.3 Proof of Lemma E.1(ii).

The proof bounds the difference between exact and estimated policy gradients by analyzing a stochastic saddle-point formulation and its estimator properties.

  • The proof compares exact and estimated gradients, x∗ = ∇θV(θ; z∗) and ˆx = ∇θ ˜V(θ; ˆz).
  • The proof decomposes the estimator analysis into bias and variance terms before combining the resulting inequalities to establish Lemma E.1(ii).
  • The stochastic saddle-point objective is strongly concave in x and strongly convex in z under the specified norms.The proof identifies µx = δ and µz = L−1.
  • Compact convex feasible regions and Lipschitz bounds allow a stochastic saddle-point generalization theorem to control the estimator error.The construction uses bounded regions for x and z, with the constrained problems sharing the original solutions.

Appendix F. Proof of Theorem 4.2

The proof maps stationarity in policy parameters to a supergradient condition in occupancy measures, then uses concavity to establish global optimality.

  • A stationary policy parameter θ∗ induces a supergradient of the concave utility composition through the chain rule.The supergradient is formed from a supergradient of F at the induced occupancy measure and the Jacobian of λ.
  • The proof transfers the stationarity condition from θ-space to the occupancy-measure space λ(Θ).It uses the representation θ = g(λ) and the Lipschitz continuity of the Jacobian ∇θλ(θ).
  • Concavity of F over the convex image λ(Θ) makes the induced occupancy measure λ∗ globally optimal.The corresponding policy θ∗ = g(λ∗) is therefore globally optimal despite the original policy-space problem being nonconvex.

G.1 Proof of sublinear convergence

The proof exploits concavity in occupancy-measure space to derive sublinear convergence, while stronger concavity yields exponential convergence under the stated assumptions.

  • The policy update analysis bounds the objective gap using concavity of F, convexity of λ(Θ), and Lipschitz continuity of the policy-to-occupancy mapping.
  • O(1/k) convergence follows after controlling the step-size recursion and bounding F(λ(π∗)) − F(λ(πk)).The proof obtains a bound proportional to 1/(k+1).
  • Strong concavity of F yields exponential convergence with a contraction factor determined by the curvature and Lipschitz constants.The proof selects a step size below one and translates the resulting gap bound into iteration complexity.
  • For tabular policies, the required mapping assumptions are supported by bijectivity and Lipschitz properties of the occupancy and policy mappings.The proof also establishes smoothness of the occupancy mapping in a neighborhood of the policy simplex.
Loading 2007.02151v1…