DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs

Khaled Nakhleh, I-Hong HouNeurIPS 2022

This NeurIPS 2022 paper introduces DeepTOP, a reinforcement learning (RL) framework designed to exploit a common structure in decision-making: the threshold policy. By focusing on problems where actions are naturally monotone, the authors derive a simplified policy gradient that allows for significantly faster and more stable learning than general-purpose RL algorithms.

TL;DR

DeepTOP is a specialized actor-critic algorithm for problems where the optimal decision depends on whether a state variable crosses a specific threshold. By leveraging the mathematical property of monotonicity, it simplifies the policy gradient, allowing it to outperform state-of-the-art methods like DDPG and TD3 in both sample efficiency and final performance across Markov Decision Processes (MDPs) and Restless Multi-Armed Bandits (RMABs).

The Problem: Generalist vs. Specialist RL

In many real-world control problems, the optimal policy is a "threshold policy." For example, a smart thermostat might turn on the AC only when the temperature exceeds a certain limit, or a bank might raise interest rates only when inflation passes a specific mark.

Standard Deep RL algorithms (like DDPG or TD3) are "generalists"—they try to learn the best action for every possible state independently. This is inefficient because it ignores the inherent structure of the problem: if it’s optimal to turn on the AC at 75°F, it is almost certainly optimal to have it on at 80°F. General RL has to "re-learn" this fact for every temperature point. Furthermore, in the context of Restless Multi-Armed Bandits (RMABs), calculating the "Whittle index"—a gold standard for prioritizing tasks—is notoriously difficult to do online.

The authors aim to bridge this gap by creating an algorithm that "knows" the policy is a threshold and uses that knowledge to speed up learning.

Methods: The Threshold Policy Gradient

The core of the paper is the Threshold Policy Gradient Theorem.

  1. The Threshold Policy: The authors define a policy where an action $a=1$ is taken if a scalar state $\lambda$ (e.g., price, temperature) is less than (or greater than) a threshold function $\mu(v)$, where $v$ represents other contextual factors.
  2. The Gradient Shortcut: Calculating the gradient of an objective function that involves an indicator function (the threshold) is usually mathematically "messy" because it involves integrals. The authors prove that for threshold policies, the gradient has a surprisingly simple expression: it depends primarily on the difference between the Q-values (expected rewards) of taking action 1 vs. action 0 exactly at the threshold.
  3. DeepTOP-MDP: This is an off-policy actor-critic algorithm. The "Actor" network learns the threshold function $\mu$, while the "Critic" network learns the Q-values.
  4. DeepTOP-RMAB: The authors show that the Whittle index is mathematically equivalent to an optimal threshold in an "alternative" version of the bandit problem. This allows them to use the same DeepTOP architecture to learn Whittle indices directly and efficiently.

Evaluated Environments

The authors evaluated DeepTOP on several simulated control problems:

  • EV Charging: Determining when to charge an electric vehicle based on fluctuating electricity prices and deadlines.
  • Inventory Management: Deciding when to order goods given seasonal demand and lead times.
  • Make-to-Stock Production: Managing a production system with different demand classes and buffer sizes.
  • RMAB Benchmarks: "One-dimensional bandits" (100-state Markov processes) and "Recovering bandits" (where a consumer's interest in a product recovers over time).
100-state Markov process for RMAB benchmarks

Key Insights

  • Monotonicity as a Superpower: By restricting the search space to monotone threshold policies, the algorithm avoids exploring "nonsensical" policies, leading to much faster convergence.
  • Direct Whittle Index Learning: Most RMAB algorithms try to learn the Whittle index indirectly through heuristics. DeepTOP treats the index itself as the threshold to be optimized, providing a more direct and theoretically grounded path to the solution.
  • Model-Free Efficiency: Despite using deep neural networks (which are often data-hungry), the structural assumptions allow DeepTOP to reach optimal performance in as few as 2,000 timesteps in some scenarios—far faster than general-purpose deep RL.

Key Results

In all MDP tests, DeepTOP significantly outperformed DDPG, TD3, and SALMUT (a specialized threshold learner). In the EV charging task, DeepTOP matched the known theoretical optimal (the "Deadline Index") almost perfectly.

Performance comparison across three environments

For multi-armed bandit problems, DeepTOP-RMAB learned effective policies much faster than recent benchmarks like NeurWIN or LPQL. Furthermore, the algorithm maintained its edge as the number of arms in the bandit problems increased (from 10 to 30 arms), suggesting it handles complexity well.

Limitations and Future Work

  • Structural Assumption: The primary limitation is that the algorithm requires the problem to admit a threshold policy. If the optimal policy is non-monotone (e.g., "do X only if the value is between 5 and 10"), DeepTOP will fail to find it.
  • Binary Actions: The current work focuses on binary action spaces (0 or 1). While many problems fit this mold, many others do not.
  • Future Directions: The authors suggest extending the framework to "multi-threshold" policies, which would allow for multiple discrete actions (e.g., a central bank choosing between a 0.25%, 0.5%, or 0.75% rate hike).

Summary updated

BibTeX
@inproceedings{nakhleh2022deeptop,
  author = {Khaled Nakhleh and I-Hong Hou},
  title = {{DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
}
Figure