Reinforcement Learning for Multi-Objective Optimization of Online Decisions in High-Dimensional Systems

Hardik Meisheri, Vinita Baniwal, Nazneen N Sultana, Balaraman Ravindran, Harshad KhadilkararXiv 2019 · arXiv

TL;DR

This paper introduces a parallelized Advantage Actor-Critic (A2C) framework designed to solve high-dimensional, multi-objective sequential decision-making problems. By cloning a single RL agent across thousands of concurrent decisions and incorporating global constraints into local reward signals, the authors successfully optimize complex retail inventory management tasks that baffle traditional optimization methods.

What Problem Does This Paper Address?

Many real-world systems, from cloud resource allocation to supply chains, require making thousands of interdependent decisions simultaneously. In retail, for instance, a store must decide how much of each product to restock daily. This is a nightmare for traditional optimization:

  • High Dimensionality: A single store might carry 100,000 products.
  • Conflicting Objectives: You want to avoid empty shelves (stock-outs) while minimizing perishable waste and ensuring "fairness" (not favoring one product's inventory over another).
  • Complex Constraints: All products for a store usually arrive on the same truck, which has strict weight and volume limits.
  • Stochasticity: Customer demand is unpredictable and non-linear.

Traditional tools like Mixed-Integer Linear Programming (MILP) don't scale well to millions of products, while classical control theory (like LQR) often requires a perfect mathematical model of the system that simply doesn't exist for complex human-driven markets.

Methods

The authors propose a data-driven approach using Reinforcement Learning (RL), specifically a modified Advantage Actor-Critic (A2C) algorithm.

1. Parallelized Decision-Making

To beat the "curse of dimensionality," the authors don't train one giant agent to output a massive vector of actions. Instead, they use a parallelized formulation: the same RL agent (with shared weights) is cloned for every product. This keeps the input space constant regardless of how many products are in the store.

2. Global-to-Local Reward Shaping

To ensure these independent "clones" work together, the reward function $R_i(t)$ for an individual product includes global terms:

  • Percentile Spread: A penalty based on the difference between the 95th and 5th percentile of inventory levels across all products to ensure fairness.
  • Capacity Penalty: A soft penalty ($\alpha \max(\rho - 1, 0)$) that triggers if the total requested volume or weight exceeds the truck's capacity.

3. Modified Training Approach

Standard A2C often uses cross-entropy loss for discrete actions. However, inventory levels are continuous. The authors quantized the action space but used a Mean Squared Error (MSE) loss on a smoothed target distribution. If the agent chooses action $j$, the target distribution is updated to favor $j$ but also gives a "boost" to neighboring actions, recognizing that a restock of 0.5 units is physically similar to 0.51 units.

Figure 2: Architecture diagram of inventory management problem.

Datasets

The researchers used a semi-synthetic dataset derived from the Instacart Market Basket Analysis public data (Kaggle).

  • Scope: Purchase data for 50,000 products and 60,000 customers.
  • Refinement: They manually assigned dimensions and weights to a subset of 220 products (representing a full grocery aisle) to simulate realistic truck constraints.
  • Timeline: 349 days of data, with restocking occurring every 6 hours (1,396 time periods total).

Key Insights and Ideas

  • Shared Intelligence: Using a single agent for all products allows the model to learn general "rules of thumb" for inventory management that apply across different items, significantly speeding up training.
  • Context is King: By including "meta-features" like a product's shelf life, unit volume, and historical forecast error in the state vector, the agent can distinguish between a gallon of milk and a box of cereal using the same neural network weights.
  • Soft vs. Hard Constraints: The agent learns to stay within truck limits via soft penalties during training, but a final "join" layer (see Figure 3 in the paper) applies a hard proportional reduction to ensure the final control vector never violates physical reality.

Key Results

The modified A2C (A2C_mod) was compared against several baselines, including a standard proportional control heuristic, vanilla A2C, DQN, and DDPG.

  • Performance: A2C_mod achieved a test reward of 0.723, significantly outperforming the standard heuristic (0.607).
  • Efficiency: While DQN achieved a slightly higher reward (0.737), A2C_mod converged much faster.
  • Scalability: DDPG, which handles continuous actions directly, struggled immensely with the high-dimensional space, requiring 7,500 episodes to reach the performance A2C_mod achieved in just 600.
  • Robustness: The agent successfully learned to minimize the "capacity overshoot," effectively learning the truck's limits through trial and error.

Limitations and Future Work

  • Forecast Dependency: The system relies on an external demand forecast. While the agent learns to handle forecast errors ($\sigma_i$), a catastrophic failure in the forecasting model would likely degrade performance.
  • Simplified Dynamics: The internal dynamics (spoilage) were modeled as a fixed proportional rate. Real-world spoilage can be more complex (e.g., temperature-dependent).
  • Future Directions: The authors suggest identifying more standard benchmarks for high-dimensional operations research to further validate the robustness of this parallelized RL approach.

Summary updated

Abstract

This paper describes a purely data-driven solution to a class of sequential decision-making problems with a large number of concurrent online decisions, with applications to computing systems and operations research. We assume that while the micro-level behaviour of the system can be broadly captured by analytical expressions or simulation, the macro-level or emergent behaviour is complicated by non-linearity, constraints, and stochasticity. If we represent the set of concurrent decisions to be computed as a vector, each element of the vector is assumed to be a continuous variable, and the number of such elements is arbitrarily large and variable from one problem instance to another. We first formulate the decision-making problem as a canonical reinforcement learning (RL) problem, which can be solved using purely data-driven techniques. We modify a standard approach known as advantage actor critic (A2C) to ensure its suitability to the problem at hand, and compare its performance to that of baseline approaches on the specific instance of a multi-product inventory management task. The key modifications include a parallelised formulation of the decision-making task, and a training procedure that explicitly recognises the quantitative relationship between different decisions. We also present experimental results probing the learned policies, and their robustness to variations in the data.
BibTeX
@misc{meisheri2019reinforcement,
  author = {Hardik Meisheri and Vinita Baniwal and Nazneen N Sultana and Balaraman Ravindran and Harshad Khadilkar},
  title = {{Reinforcement Learning for Multi-Objective Optimization of Online Decisions in High-Dimensional Systems}},
  year = {2019},
  eprint = {1910.00211},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1910.00211},
}

Loading related content...

Figure