# Online Reinforcement Learning of Optimal Threshold Policies for Markov Decision Processes

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Dec 2019.

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

- [A Small Gain Analysis of Single Timescale Actor Critic](https://mlsanity.com/paper/2203.02591/) (2022)
- [Intrusion Prevention through Optimal Stopping](https://mlsanity.com/paper/2111.00289/) (2021)
- [Learning Intrusion Prevention Policies through Optimal Stopping](https://mlsanity.com/paper/2106.07160/) (2021)
- [DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs](https://mlsanity.com/paper/2209.08646/) (2022)
- [Structure-aware reinforcement learning for node-overload protection in mobile edge computing](https://mlsanity.com/paper/2107.01025/) (2021)
- [Structured Reinforcement Learning for Media Streaming at the Wireless Edge](https://mlsanity.com/paper/2404.07315/) (2024)
- [Optimizing Predictive Maintenance in Intelligent Manufacturing: An Integrated FNO-DAE-GNN-PPO MDP Framework](https://mlsanity.com/paper/2511.05594/) (2025)

## Abstract (arXiv)

To overcome the curses of dimensionality and modeling of Dynamic Programming (DP) methods to solve Markov Decision Process (MDP) problems, Reinforcement Learning (RL) methods are adopted in practice. Contrary to traditional RL algorithms which do not consider the structural properties of the optimal policy, we propose a structure-aware learning algorithm to exploit the ordered multi-threshold structure of the optimal policy, if any. We prove the asymptotic convergence of the proposed algorithm to the optimal policy. Due to the reduction in the policy space, the proposed algorithm provides remarkable improvements in storage and computational complexities over classical RL algorithms. Simulation results establish that the proposed algorithm converges faster than other RL algorithms.