# Computing Complexity-aware Plans Using Kolmogorov Complexity

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 44 references that are in the map.
- First posted on arXiv 21 Sep 2021.

## Builds on (most cited first, 11 of 11)

- [Policy Distillation](https://mlsanity.com/paper/1511.06295/) (2015)
- [A Tour of Reinforcement Learning: The View from Continuous Control](https://mlsanity.com/paper/1806.09460/) (2018)
- [AI Feynman 2.0: Pareto-optimal symbolic regression exploiting graph modularity](https://mlsanity.com/paper/2006.10782/) (2020)
- [Learning Discrete State Abstractions With Deep Variational Inference](https://mlsanity.com/paper/2003.04300/) (2020)
- [A Strongly Asymptotically Optimal Agent in General Environments](https://mlsanity.com/paper/1903.01021/) (2019)
- [LQG Control with Minimum Directed Information: Semidefinite Programming Approach](https://mlsanity.com/paper/1510.04214/) (2015)
- [Universal Reinforcement Learning Algorithms: Survey and Experiments](https://mlsanity.com/paper/1705.10557/) (2017)
- [Transfer-Entropy-Regularized Markov Decision Processes](https://mlsanity.com/paper/1708.09096/) (2017)
- [Minimum-Information LQG Control - Part I: Memoryless Controllers](https://mlsanity.com/paper/1606.01946/) (2016)
- [Learning to Actively Reduce Memory Requirements for Robot Control Tasks](https://mlsanity.com/paper/2008.07451/) (2020)
- [Algorithmic Design for Embodied Intelligence in Synthetic Cells](https://mlsanity.com/paper/2006.07244/) (2020)

## Built on by (most cited first, 2 of 2)

- [Reinforcement Learning with Almost Sure Constraints](https://mlsanity.com/paper/2112.05198/) (2021)
- [Predictable Reinforcement Learning Dynamics through Entropy Rate Minimization](https://mlsanity.com/paper/2311.18703/) (2023)

## Abstract (arXiv)

In this paper, we introduce complexity-aware planning for finite-horizon deterministic finite automata with rewards as outputs, based on Kolmogorov complexity. Kolmogorov complexity is considered since it can detect computational regularities of deterministic optimal policies. We present a planning objective yielding an explicit trade-off between a policy's performance and complexity. It is proven that maximising this objective is non-trivial in the sense that dynamic programming is infeasible. We present two algorithms obtaining low-complexity policies, where the first algorithm obtains a low-complexity optimal policy, and the second algorithm finds a policy maximising performance while maintaining local (stage-wise) complexity constraints. We evaluate the algorithms on a simple navigation task for a mobile robot, where our algorithms yield low-complexity policies that concur with intuition.