A Fitted-Q Algorithm for Budgeted MDPs

Nicolas Carrara, Romain Laroche, Jean-Léon Bouraoui, Tanguy Urvoy, Olivier PietquinHAL 2018

TL;DR

This paper introduces Budgeted Fitted-Q (BFTQ), a novel algorithm for reinforcement learning (RL) in scenarios with budget constraints. BFTQ allows agents to learn policies that optimize rewards while adhering to a budget, directly from data and without requiring environment simulations during training. This is a significant step towards applying RL to real-world problems with inherent resource limitations.

What Problem Does This Paper Address?

Traditional reinforcement learning algorithms focus on maximizing a single expected reward. However, many real-world applications involve multiple, potentially conflicting objectives, or require operating within strict resource constraints. For instance, an autonomous vehicle needs to minimize travel time and fuel consumption while ensuring safety. This paper specifically addresses Budgeted Markov Decision Processes (BMDPs), where the goal is to find a policy that maximizes cumulative reward while ensuring that a cumulative cost stays below a predefined budget. Existing methods often struggle with continuous state spaces, require environment simulations for policy tuning, or are not directly applicable to the BMDP framework. This work aims to bridge this gap by providing a data-driven, continuous-state RL algorithm for BMDPs.

Methods

The core contribution is the Budgeted Fitted-Q (BFTQ) algorithm, an extension of the Fitted-Q (FTQ) algorithm. BFTQ tackles BMDPs by approximating two key functions:

  • Reward Q-function ($Q_r$): Estimates the expected discounted sum of rewards.
  • Constraint Q-function ($Q_c$): Estimates the expected discounted sum of costs.

Both functions are defined over a state-action-budget triplet. BFTQ trains these Q-functions using a batch of transitions, similar to FTQ. A key innovation is how BFTQ handles the budget constraint during policy execution. Instead of relying on a separate calibration phase (as in penalized FTQ), BFTQ directly learns a budget policy ($b$) that determines how to allocate the remaining budget for each state-action pair. This allows for more flexible and adaptive policies.

To efficiently solve the optimization problem arising from the budget constraint, the authors introduce an algorithm called SOLVE. This algorithm leverages the concave and increasing nature of the Q-functions with respect to the budget to efficiently find the optimal policy by analyzing the convex hull of discretized Q-function values.

Datasets

The paper does not introduce new datasets. Instead, it uses simulated environments for training and evaluation. Specifically, they experiment on:

  • 2-D worlds with forbidden areas: Used for initial benchmarking.
  • N x N 2-D worlds: These are randomly generated worlds with continuous state spaces, where the agent starts at (0,0) and aims to reach (N-1, N-1) for a reward, while avoiding randomly placed "holes" that incur a constraint penalty.

Key Insights and Ideas

  • Directly learning budget-aware policies: BFTQ's ability to learn a budget policy alongside the reward policy is a significant advantage, eliminating the need for separate, often difficult, calibration steps.
  • Data-driven approach: The algorithm learns directly from a batch of transitions, making it suitable for scenarios where environment interaction during training is costly or impossible.
  • Exploiting Q-function properties: The observation that $Q_r$ and $Q_c$ are concave and increasing with budget is crucial for developing an efficient solver (SOLVE) for the underlying optimization problem.
  • Flexibility in budget adaptation: BFTQ's learned policies can adapt to changing budget scenarios without retraining, which is valuable for dynamic environments.

Key Results

  • Comparable performance to penalized FTQ: In experiments on 5x5 2-D worlds, BFTQ achieved similar reward returns to a penalized FTQ algorithm for equivalent constraint returns.
  • Reduced sensitivity to hyperparameter tuning: BFTQ requires specifying a budget, whereas penalized FTQ requires careful tuning of the penalty parameter ($\lambda$), which can be difficult to calibrate across different environments.
  • Less noisy policies: BFTQ's policies were observed to be less noisy than FTQ's, likely due to the fixed budget-based approach versus the environment-dependent $\lambda$ tuning.
  • Successful execution in complex worlds: Experiments on 10x10 worlds demonstrated that BFTQ can learn effective policies, with policy execution showing agents stopping prematurely for low budgets and reaching goals for higher budgets.

Limitations and Future Work

  • Approximation of policies: The paper acknowledges that approximating the optimal behavioral and budget policies using regression on training transitions is a simplification. The authors suggest that finding a closed-form solution for the optimization problem (Eq. 15) could significantly speed up computation and improve policy approximation.
  • Conjecture on separability: The assumption that optimization problems in tree-shaped BMDPs can be separated into independent sub-problems is stated as a conjecture for general BMDPs with loops.
  • Discretization of budget: The SOLVE algorithm relies on a discretization of the budget, which might introduce some approximation error.
  • Future work: The authors suggest extending this approach to other classic RL algorithms and exploring closed-form solutions for the policy optimization. They also believe this framework could be extended to handle more complex risk-sensitive scenarios beyond average-case constraints.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{carrara2018fitted,
  author = {Nicolas Carrara and Romain Laroche and Jean-Léon Bouraoui and Tanguy Urvoy and Olivier Pietquin},
  title = {{A Fitted-Q Algorithm for Budgeted MDPs}},
  booktitle = {HAL},
  year = {2018},
}
Figure