PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learning

Kyungjae Lee, Sungjoon Choi, Songhwai Oh

arXiv:1709.06293v3cs.LGcs.AIstat.ML

TL;DR

Deterministic optimal policies do not represent multiple optimal actions, while softmax policies can retain probability on non-optimal actions as action counts grow. The paper proposes causal sparse Tsallis entropy regularization and sparse value iteration, then proves a constant performance-error bound for sparse MDPs versus logarithmic growth for soft MDPs and reports better performance as action counts increase. It presents sparse MDPs as an alternative for problems with many possible actions, including continuous action spaces.

  • Problem

    Deterministic optimal policies cannot represent multiple optimal actions, and softmax policies can assign non-negligible mass to non-optimal actions as the number of actions increases.

    Source: §I · p. 1

  • Method

    The paper introduces causal sparse Tsallis entropy regularization and derives a sparse Bellman equation and sparse value iteration for solving sparse MDPs.

    Source: §I · p. 1

  • Results

    Sparse MDP performance error has a constant bound as action counts increase, compared with logarithmic growth for soft MDPs; experiments report significantly better performance than ϵ-greedy, softmax exploration, and DDPG as action counts increase.

    Source: §I · p. 1, §VIII · p. 8

  • Takeaways & Limitations

    The analysis and experiments support sparse MDPs as an efficient alternative for problems with many possible actions, including continuous action spaces.

    Source: §VIII · p. 8

Abstract

from arXiv · show

In this paper, a sparse Markov decision process (MDP) with novel causal sparse Tsallis entropy regularization is proposed.The proposed policy regularization induces a sparse and multi-modal optimal policy distribution of a sparse MDP. The full mathematical analysis of the proposed sparse MDP is provided.We first analyze the optimality condition of a sparse MDP. Then, we propose a sparse value iteration method which solves a sparse MDP and then prove the convergence and optimality of sparse value iteration using the Banach fixed point theorem. The proposed sparse MDP is compared to soft MDPs which utilize causal entropy regularization. We show that the performance error of a sparse MDP has a constant bound, while the error of a soft MDP increases logarithmically with respect to the number of actions, where this performance error is caused by the introduced regularization term. In experiments, we apply sparse MDPs to reinforcement learning problems. The proposed method outperforms existing methods in terms of the convergence speed and performance.

I. INTRODUCTION

MDPs provide a framework for sequential decision problems, but deterministic optimal policies cannot represent multiple optimal actions or multimodal expert behavior. The paper proposes causal sparse Tsallis entropy regularization to retain multiple modes while limiting non-optimal action mass as the action space grows.

I. INTRODUCTION

  • Causal sparse Tsallis entropy regularization yields sparse policies, while the paper analyzes their optimality and compares their performance error with soft MDPs.The sparse MDP error has a constant bound as the number of actions increases, whereas the soft MDP error grows logarithmically.Source: §I · p. 1

A. Markov Decision Processes

  • An MDP seeks a policy maximizing expected discounted rewards, and its unregularized optimal policy is deterministic.MDPs are used to formulate reinforcement learning and inverse reinforcement learning problems.Source: §I · p. 1, A. Markov Decision Processes · p. 2

B. Entropy Regularized Markov Decision Processes

  • Causal entropy regularization makes a soft MDP's optimal policy a softmax distribution, but softmax can retain non-negligible mass on non-optimal actions as action counts grow.The paper motivates sparse regularization as a way to retain multiple modes while reducing performance loss relative to softmax.Source: §I · p. 1, B. Entropy Regularized Markov Decision… · pp. 2–3

III. SPARSE MARKOV DECISION PROCESSES

The paper formulates a sparse MDP using causal sparse Tsallis entropy regularization and derives its optimality conditions. KKT conditions yield a sparse Bellman equation whose policy assigns probability selectively to actions.

III. SPARSE MARKOV DECISION PROCESSES

  • A causal sparse Tsallis regularizer defines the sparse MDP, with regularization strength controlling the sparsity of its optimal policy.The paper derives the sparse Bellman equation from the necessary condition of the optimization problem.Source: §III · p. 3

A. Notations and Properties

B. Sparse Bellman Equation from Karush-Kuhn-Tucker conditions

  • KKT conditions yield a sparse Bellman equation that zeros below-threshold actions, weights near-optimal actions, and connects the policy to simplex projection.The threshold determines the range of near-optimal actions receiving positive probability.Source: B. Sparse Bellman Equation from… · p. 3

C. Probability Simplex Projection and SparseMax Operation

The paper connects sparse Bellman policies to Euclidean simplex projection, yielding sparsemax distributions. It also describes how regularization controls the action support and relates the causal regularizer to Tsallis entropy.

C. Probability Simplex Projection and SparseMax Operation

  • Euclidean simplex projection turns state-action values into sparsemax policy probabilities; the associated sparsemax value is a bounded smooth approximation of max.The projection has a closed-form solution that assigns zero probability below its threshold.Source: C. Probability Simplex Projection and… · p. 4

D. Supporting Set of Sparse Optimal Policy

  • The regularization coefficient controls support size: increasing it expands the sparse policy's support, while softmax support remains the entire action space.At the extremes, zero regularization leaves only the highest-valued action in the support, while infinite regularization includes all actions.Source: D. Supporting Set of Sparse Optimal… · pp. 4–5

E. Connection to Tsallis Generalized Entropy

  • The causal policy regularizer extends Tsallis entropy with parameters q = 2 and k = 1/2.The paper presents this as a Tsallis-entropy extension to causally conditioned distributions.Source: E. Connection to Tsallis Generalized… · p. 5

IV. SPARSE VALUE ITERATION

Sparse value iteration repeatedly applies a sparse Bellman operator, whose contraction guarantees convergence to the sparse MDP’s optimal value. The paper also bounds regularization-related performance error, finding tighter bounds for sparse MDPs than for soft MDPs as action counts grow.

A. Optimality of Sparse Value Iteration

  • Sparse value iteration converges to the optimal value of the sparse MDP by repeatedly applying its Bellman operator.The operator is a γ-contraction with a unique fixed point, established from its monotonicity and discounting properties.Source: A. Optimality of Sparse Value Iteration · p. 5

V. PERFORMANCE ERROR BOUNDS FOR SPARSE VALUE ITERATION

  • Sparse and soft regularized policy values are at least the original MDP’s optimal value, with the added regularization term accounting for the inequality.The paper attributes this relation to W(π) for sparse MDPs and H(π) for soft MDPs.Source: §V · p. 6
  • Sparse MDP performance-error bounds remain constant as the action count grows, while soft MDP bounds grow logarithmically; the sparse bounds are tighter.This distinction matters for fine discretizations of continuous action spaces, where the number of actions increases.Source: §V · p. 6

VI. SPARSE EXPLORATION AND UPDATE RULE FOR SPARSE DEEP Q-LEARNING

Sparse Q-learning uses the sparse Bellman equation to estimate the sparse MDP’s optimal action values without knowing transition probabilities. Its deep variant uses sparsemax for exploration and a sparse Bellman update.

VI. SPARSE EXPLORATION AND UPDATE RULE FOR SPARSE DEEP Q-LEARNING

  • Sparse deep Q-learning combines a sparse Bellman update with sparsemax exploration, which assigns zero probability to actions whose estimated values are too low to re-explore.The deep variant estimates sparse Q values with a neural network and minimizes squared loss using gradient descent.Source: §VI · pp. 6–7
  • Sparse Q-learning estimates the sparse MDP’s optimal Q values from sampled transitions without requiring known transition probabilities.With the stated learning-rate conditions, it converges to the sparse MDP’s optimal solution as samples increase.Source: §VI · pp. 6–7

VII. EXPERIMENTS

The experiments report that sparsemax exploration compares favorably with ϵ-greedy, softmax, and DDPG, while unicycle simulations show bounded sparse-MDP performance gaps and sparser supporting sets than soft MDPs. Tests use discretized continuous-action problems.

A. Experiments on Performance Bounds and Supporting Set

  • In unicycle simulations, sparse-MDP performance gaps converge to a constant bound while soft-MDP gaps grow logarithmically, and sparse MDPs have smaller supporting-set ratios across the tested α range.The sparse ratio ranges from 0.24 to 0.99, compared with 0.79 to 1.00 for soft MDPs.Source: A. Experiments on Performance Bounds… · p. 7

VII. EXPERIMENTS

  • The reinforcement-learning tests use MuJoCo inverted-pendulum and reacher problems with continuous action spaces discretized at four levels.The comparison includes 27 deep Q-learning variants and DDPG.Source: B. Reinforcement Learning in a… · pp. 7–8

B. Reinforcement Learning in a Continuous Action Space

  • For inverted pendulum, most top-five algorithms reach the maximum return of 1000 at each discretization level, and sparsemax exploration needs fewer episodes than ϵ-greedy or softmax to reach 980.The plotted results average three independent runs.Source: B. Reinforcement Learning in a… · p. 8, Figure 3 · p. 8
  • For reacher, sparsemax methods slightly outperform ϵ-greedy in performance and require fewer episodes to reach −6; softmax does not appear among the top five.DDPG performs poorly in both tested problems, which the authors attribute to insufficient sampled episodes.Source: B. Reinforcement Learning in a… · p. 8, Figure 4 · p. 8

VIII. CONCLUSION

  • The conclusion reports that sparsemax exploration performs better than ϵ-greedy, softmax, and DDPG as the number of actions increases.The experiments apply sparsemax as the exploration strategy and the sparse Bellman equation as the update rule in deep Q-learning.Source: §VIII · p. 8

APPENDIX A

The appendix derives the sparse Bellman equation’s optimality condition from KKT conditions, using the supporting set of actions with positive policy probability.

A. Sparse Bellman Equation from Karush-Kuhn-Tucker conditions

  • The appendix derives the sparse MDP optimality condition from the KKT conditions of the optimization problem.It identifies primal and dual feasibility, complementary slackness, and stationarity among the KKT conditions.Source: A. Sparse Bellman Equation from… · pp. 8–9
  • The supporting set S(s) consists of actions whose values exceed a threshold, and it is used to express the optimal policy distribution.The derivation uses the number of positive policy probabilities to obtain the Lagrangian multiplier.Source: A. Sparse Bellman Equation from… · p. 9
  • Substituting the optimal policy distribution yields the sparse Bellman equation.The equation gives the sparse MDP’s optimality condition.Source: A. Sparse Bellman Equation from… · p. 9

B. Upper and Lower Bounds for Sparsemax Operation

The section establishes lower and upper bounds for sparsemax, locating its value between the maximum input and a dimension-dependent additive bound. The lower-bound proof shows the difference from the maximum is nonnegative.

B. Upper and Lower Bounds for Sparsemax Operation

  • For all z in R^d, max(z) ≤ spmax(z).The proof reduces the lower bound to showing spmax(z) − z(1) ≥ 0, where z(1) = max(z).Source: B. Upper and Lower Bounds for… · p. 9
  • The lower-bound proof rearranges the expression into three nonnegative terms, using Cauchy–Schwarz to establish nonnegativity of the second term.The first and third terms are quadratic and nonnegative.Source: B. Upper and Lower Bounds for… · p. 10
  • For every z in R^d, the stated SparseMax upper bound is spmax(z) ≤ max(z) + d−1; the cited expression gives no further fraction or denominator.The derivation specifies d ≥ K by definition of K.Source: B. Upper and Lower Bounds for… · pp. 10–11

C. Comparison to Log-Sum-Exp

Sparsemax has tighter approximation bounds than log-sum-exp: its error is bounded by a dimension-dependent term that approaches 1/2, while log-sum-exp’s bound grows with the action-space dimension.

C. Comparison to Log-Sum-Exp

  • Log-sum-exp is bounded between max(z) and max(z) + log(d).The upper bound makes its approximation error increase with input dimension.Source: C. Comparison to Log-Sum-Exp · p. 11
  • The cited passages state that sparsemax has tighter bounds than log-sum-exp for all d > 1, but do not give a complete inequality for that comparison.Source: C. Comparison to Log-Sum-Exp · p. 11
  • Sparsemax’s approximation error approaches 1/2 as the input dimension tends to infinity, unlike the growing log-sum-exp bound.The section notes that this distinction matters for comparing sparse- and soft-MDP performance error bounds.Source: C. Comparison to Log-Sum-Exp · p. 11

D. Causal Sparse Tsallis Entropy

The causal sparse Tsallis regularizer is a special case of Tsallis generalized entropy with q = 2 and k = 1. Sparse value iteration converges to the unique optimal value of the sparse MDP.

D. Causal Sparse Tsallis Entropy

  • The causal sparse Tsallis regularization is equivalent to discounted expected Tsallis entropy with q = 2 and k = 1.The equivalence is established by rewriting the regularization.Source: D. Causal Sparse Tsallis Entropy · p. 11

E. Convergence and Optimality of Sparse Value Iteration

  • The sparse Bellman operation is a γ-contraction, yielding a unique fixed point in the complete metric space described.The proof uses monotonicity and discounting properties.Source: E. Convergence and Optimality of… · p. 12
  • Sparse value iteration converges to the unique optimal value of a sparse MDP.Its fixed point satisfies the sparse Bellman equation and the optimality conditions; uniqueness follows from the Banach fixed point theorem.Source: E. Convergence and Optimality of… · p. 12

F. Performance Error Bounds for Sparse Value Iteration

The section derives performance error bounds by comparing sparse and soft value iteration with the original MDP. The soft-MDP bound includes a term that grows with the logarithm of the number of actions.

F. Performance Error Bounds for Sparse Value Iteration

APPENDIX B

Appendix B reports full experimental results for continuous-action reinforcement learning on Inverted Pendulum and Reacher, testing 28 algorithms including the proposed methods.

  • The section presents full experimental results for continuous-action reinforcement learning.Source: Appendix B · p. 13
  • Experiments cover Inverted Pendulum and Reacher.Source: Appendix B · p. 13
  • The evaluation tests 28 algorithms, including sparse exploration and the sparse Bellman update rule.Source: Appendix B · p. 13

Related papers

Loading 1709.06293v3…