Regret Minimization for Reinforcement Learning with Vectorial Feedback and Complex Objectives

Wang Chi CheungNeurIPS 2019 · OpenReview

Introduction

In standard Reinforcement Learning (RL), an agent typically receives a single scalar reward and attempts to maximize its cumulative sum over time. However, real-world tasks often involve multiple competing objectives. For example, a navigating robot must simultaneously balance speed, battery efficiency, and safety.

This paper introduces a novel framework for RL where agents receive multi-dimensional "vectorial" feedback rather than a single scalar reward. To maximize complex, non-linear aggregate objectives in an unknown environment, the author proposes TFW-UCRL2, an algorithm that utilizes a unique "Gradient Threshold Procedure" to prevent the agent from wasting time switching between states too frequently.

The Challenge of Complex Objectives in MDPs

When multiple objectives are tied to different physical states in a Markov Decision Process (MDP), a unique challenge arises. To "balance" these objectives, the agent must physically travel between different parts of the environment. If the agent attempts to adjust its strategy too frequently (e.g., after every single step), it risks spending all its time in "bridge" states—transitional states that contribute nothing to its actual goals.

This challenge is further complicated by model uncertainty. Initially, the agent does not know the transition dynamics of the environment or where the optimal rewards are located. The paper formalizes this setting as the Complex-Objective Online MDP (CO-OMDP) problem, where the goal is to maximize a concave function of the average vectorial outcome over time.

Comparison of Bandits with Rewards (BwR), Complex-Objective Online MDP (CO-OMDP), and Scalar-Objective Online MDP (SO-OMDP).

Methodology: The TFW-UCRL2 Algorithm

The author proposes TFW-UCRL2, an algorithm that elegantly combines three distinct components to solve the CO-OMDP problem:

  1. Frank-Wolfe (FW) Algorithm: A classic optimization method used here to "scalarize" the vector feedback. It calculates a gradient based on the current average performance, effectively telling the agent which specific objective requires more focus at any given moment.
  2. UCRL2 (Upper Confidence Bound for RL): A standard algorithm for handling model uncertainty. It builds a "confidence region" of possible MDP models and acts optimistically, choosing the best possible policy within those bounds to encourage exploration.
  3. Gradient Threshold Procedure (GTP): This is the core innovation of the paper. Instead of updating the agent's policy every time the Frank-Wolfe gradient changes, GTP intentionally delays the update until the gradient has shifted by a specific threshold ($Q$). This "laziness" ensures the agent commits to a stationary policy long enough to actually collect rewards, rather than constantly oscillating and getting trapped in transition states.

Key Insights and Theoretical Guarantees

  • Sub-optimality of Stationary Policies: Unlike standard RL, where a single "best" fixed policy usually exists, complex objectives inherently require the agent to switch between different policies over time to balance diverse outcomes.
  • The Cost of Switching: In an MDP, changing strategies incurs a physical cost (traveling to a new state). The paper mathematically proves that without a mechanism like GTP to limit switching, an agent can suffer "linear regret," meaning it fails to learn the optimal behavior.
  • Judicious Delay Yields No-Regret: By carefully delaying gradient updates via the threshold $Q$, the agent achieves a "no-regret" bound. The paper proves an anytime regret bound of $\tilde{O}(T^{-1/2})$. This matches the best possible rates for simpler versions of the problem, demonstrating that the added complexity of vectorial feedback does not fundamentally degrade asymptotic learning rates.
  • Bridging Bandits and MDPs: The work successfully connects "Bandits with global concave rewards" (which lack state transitions) with "Scalar-Objective MDPs" (which lack complex objectives), providing a unified theoretical approach.

Empirical Results

The paper evaluates the algorithm using synthetic State Space Exploration environments (categorized as Small, Medium, and Large). The objective in these tests is to visit specific states with target frequencies.

In simulations, TFW-UCRL2 successfully converged to target frequencies even when those targets were physically impossible to reach perfectly, gracefully finding the "next best" feasible solution. Furthermore, experiments highlighted the critical importance of the threshold parameter $Q$. If $Q$ is too small, the agent switches too much; if it is too large, the agent fails to adapt fast enough. The theoretical default value provided by the author proved robust across different environment sizes.

Limitations and Future Work

While a significant step forward, the framework has a few limitations:

  • Communicating MDP Assumption: The theory relies on the environment being a "communicating" MDP (it is possible to travel from any state to any other state). Environments with dead ends or irreversible transitions may cause the algorithm to fail.
  • Concave Objectives: The current framework requires the aggregate reward function to be concave. While this covers many practical use cases like fairness or meeting KPIs, it does not extend to non-concave objectives.
  • Parameter Tuning and Scalability: While a default $Q$ is provided, dynamically tuning $Q$ online remains an open research direction. Additionally, testing this approach on high-dimensional continuous control tasks (such as complex robotics) will be a crucial next step for real-world applicability.

Summary updated

Abstract

We consider an agent who is involved in an online Markov decision process, and receives a vector of outcomes every round. The agent aims to simultaneously optimize multiple objectives associated with the multi-dimensional outcomes. Due to state transitions, it is challenging to balance the vectorial outcomes for achieving near-optimality. In particular, contrary to the single objective case, stationary policies are generally sub-optimal. We propose a no-regret algorithm based on the Frank-Wolfe algorithm (Frank and Wolfe 1956), UCRL2 (Jaksch et al. 2010), as well as a crucial and novel gradient threshold procedure. The procedure involves carefully delaying gradient updates, and returns a non-stationary policy that diversifies the outcomes for optimizing the objectives.
BibTeX
@inproceedings{cheung2019regret,
  author = {Wang Chi Cheung},
  title = {{Regret Minimization for Reinforcement Learning with Vectorial Feedback and Complex Objectives}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=k7obTelKRB},
}
Figure