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

arXiv: https://arxiv.org/abs/1709.06293 · HTML: https://mlsanity.com/paper/1709.06293/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2017.

## Built on by (most cited first, 30 of 37)

- [Imitation Learning as f-Divergence Minimization](https://mlsanity.com/paper/1905.12888/) (2019)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Twice regularized MDPs and the equivalence between robustness and regularization](https://mlsanity.com/paper/2110.06267/) (2021)
- [Policy Gradient for Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13589/) (2023)
- [Estimating Optimal Infinite Horizon Dynamic Treatment Regimes via pT-Learning](https://mlsanity.com/paper/2110.10719/) (2021)
- [Your Policy Regularizer is Secretly an Adversary](https://mlsanity.com/paper/2203.12592/) (2022)
- [Identifiability and Generalizability in Constrained Inverse Reinforcement Learning](https://mlsanity.com/paper/2306.00629/) (2023)
- [KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/2205.14211/) (2022)
- [Maximum Causal Tsallis Entropy Imitation Learning](https://mlsanity.com/paper/1805.08336/) (2018)
- [Continuous-time q-Learning for Jump-Diffusion Models under Tsallis Entropy](https://mlsanity.com/paper/2407.03888/) (2024)
- [Quasi-optimal Reinforcement Learning with Continuous Actions](https://mlsanity.com/paper/2301.08940/) (2023)
- [A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search](https://mlsanity.com/paper/2202.07071/) (2022)
- [Hard Prompts Made Interpretable: Sparse Entropy Regularization for Prompt Tuning with RL](https://mlsanity.com/paper/2407.14733/) (2024)
- [Roping in Uncertainty: Robustness and Regularization in Markov Games](https://mlsanity.com/paper/2406.08847/) (2024)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Robust Entropy-regularized Markov Decision Processes](https://mlsanity.com/paper/2112.15364/) (2021)
- [Planning and Learning Using Adaptive Entropy Tree Search](https://mlsanity.com/paper/2102.06808/) (2021)
- [Reinforcement Learning With Sparse-Executing Actions via Sparsity Regularization](https://mlsanity.com/paper/2105.08666/) (2021)
- [Regularized Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2401.15196/) (2024)
- [q-exponential family for policy optimization](https://mlsanity.com/paper/2408.07245/) (2024)
- [Learning Personalized Prompts for Healthcare Guidance](https://mlsanity.com/paper/2412.15957/) (2024)
- [Generalized Munchausen Reinforcement Learning using Tsallis KL Divergence](https://mlsanity.com/paper/2301.11476/) (2023)
- [Differentiable Arbitrating in Zero-sum Markov Games](https://mlsanity.com/paper/2302.10058/) (2023)
- [Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization](https://mlsanity.com/paper/2303.06654/) (2023)
- [Optimal Rates of Convergence for Entropy Regularization in Discounted Markov Decision Processes](https://mlsanity.com/paper/2406.04163/) (2024)
- [Continuous-time q-learning for Markov regime switching system under Tsallis entropy](https://mlsanity.com/paper/2601.19299/) (2026)
- [Perspectives on Tsallis Statistics for Artificial Intelligence](https://mlsanity.com/paper/2608.01223/) (2026)
- [q-Munchausen Reinforcement Learning](https://mlsanity.com/paper/2205.07467/) (2022)
- [Enforcing KL Regularization in General Tsallis Entropy Reinforcement Learning via Advantage Learning](https://mlsanity.com/paper/2205.07885/) (2022)

## Abstract (arXiv)

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.