🤖 machine learning

Modelling Customer Trajectories with Reinforcement Learning for Practical Retail Insights

This paper proposes a maximum entropy reinforcement learning framework for modeling customer trajectories in retail spaces, demonstrating that it outperforms traditional heuristics like TSP and PNN by providing more accurate, behaviorally grounded insights for store layout optimization and profit maximization without requiring costly real-world data collection.

Original authors: Ken Ming Lee, Paul Barde, Maxime C. Cohen, Derek Nowrouzezahrai

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ken Ming Lee, Paul Barde, Maxime C. Cohen, Derek Nowrouzezahrai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you own a small convenience store. Your goal is simple: make as much money as possible. You know that people often buy things they didn't plan to buy—like a candy bar or a soda—just because they saw it while walking down the aisle. This is called an "impulse purchase."

To get people to buy these items, you need to know exactly where they walk. If you put the candy bar right in their path, they'll grab it. If you hide it in a corner they never visit, they won't.

The Problem: The "Guessing Game" vs. The "Expensive Spy"
To figure out where customers walk, you have two bad options:

The Spy (Real Data): You hire people to follow customers around with cameras and maps. This gives you perfect information, but it's incredibly expensive and invasive. Most small stores can't afford this.
The Guess (Heuristics): You use simple math rules to guess the path.
- The "Shortest Path" Rule (TSP): This assumes customers are robots who always take the absolute shortest route to get their items.
- The "Nearest Neighbor" Rule (PNN): This assumes customers are a bit random but still mostly pick the closest item to them.

The paper found that these "guessing" rules are wrong about 28% of the time. Real people are messy. They wander, they take detours, and they don't always take the shortest path. Because the guesses are so off, store owners end up putting products in the wrong spots, missing out on sales.

The Solution: A "Video Game" Student
The authors created a new way to predict customer paths using Reinforcement Learning (RL). Think of this like training a video game character (an "agent") to act like a real human shopper.

Instead of just telling the character to "take the shortest path," they taught it a more human lesson:

Get the items: You get points for buying what you need.
Be a little unpredictable: You also get points for exploring different routes, not just the same boring one every time.

This is called "Maximum Entropy" learning. It forces the computer to realize that humans aren't robots; we have "bounded rationality." We make mistakes, we get distracted, and we take different paths even when buying the same things.

What They Did
They took real data from a convenience store (where they tracked 3,000+ real shoppers) and used it to train their "video game student." Then, they asked the student to simulate 10,000 shopping trips.

The Results: The Student Wins
When they compared the "video game student's" paths to the real human paths:

The "Shortest Path" rule failed miserably. It missed entire sections of the store because it only looked for the fastest route.
The "Nearest Neighbor" rule was better but still missed the "wandering" behavior of real people.
The RL Student was the closest match. It figured out that sometimes people walk through the bottom of the store even if the top is shorter, just because that's how they like to shop.

Why This Matters for Your Wallet
The paper tested this by trying to move a specific product (like Soft Drinks) to a new shelf to make more money.

If you used the Shortest Path or Nearest Neighbor guesses, they told you to move the product to a shelf that was actually empty and rarely visited. This would have been a waste of space.
The RL Student correctly identified the busy, high-traffic shelves that real humans actually walk past.

When they moved the product to the spot the RL student suggested, the store made almost as much extra profit as if they had used the expensive "Spy" data. The simple guessing rules failed to find the right spot.

The Bottom Line
This paper shows that you don't need to spend a fortune tracking every customer with cameras to optimize your store. Instead, you can use a smart computer model that learns to "think" like a human shopper. It bridges the gap between "too simple to be true" (the guessing rules) and "too expensive to be practical" (real data), giving store owners a cheap, accurate way to arrange their shelves for maximum profit.

Technical Summary: Modelling Customer Trajectories with Reinforcement Learning for Practical Retail Insights

1. Problem Statement

The central goal of retail store layout optimization is maximizing profit, primarily driven by impulse purchases (spontaneous buys influenced by product placement and exposure). To optimize layouts, retailers must understand customer movement patterns (trajectories). However, collecting real-world trajectory data is costly and often infeasible, particularly for smaller retailers.

Consequently, the industry relies on inexpensive heuristic approximations:

Travelling Salesman Problem (TSP): Assumes customers take the globally shortest path.
Probabilistic Nearest Neighbour (PNN): Models a stochastic greedy route where the next item is chosen based on proximity.

The Gap: Prior research indicates that actual customer trajectories deviate from shortest-path estimates by an average of 28%. This creates a tradeoff: heuristics are cheap but unrealistic (failing to capture behavioral variability and bounded rationality), while real data is accurate but prohibitively expensive. The paper seeks to bridge this gap by proposing a method that is more behaviorally accurate than heuristics but more accessible than collecting new ground-truth data.

2. Methodology

The authors propose an agent-based modelling framework where customer trajectory prediction is cast as a Maximum Entropy Reinforcement Learning (MaxEnt RL) problem.

2.1 Environment and Data

Data Source: Anonymized 3D joint coordinates and checkout baskets from a convenience store (collected Sept 2023–Feb 2024).
Discretization: The store is modeled as a $16 \times 36$ grid (50cm per cell). The dataset focuses on the top 61 best-selling products across 11 categories.
Preprocessing: Trajectories are normalized to start at the entrance and end at a checkout. Invalid points are corrected, and trajectories are transformed into $(state, action)$ sequences.

2.2 RL Formulation

Agent: Customers are modeled as conditional MaxEnt RL agents trained using Proximal Policy Optimization (PPO) with a convolutional neural network backbone.
Objective: The agent maximizes expected cumulative reward while simultaneously maximizing policy entropy. This dual objective encourages the agent to find diverse, task-valid paths rather than a single deterministic shortest path, effectively modeling bounded rationality.
Observations: The agent observes a multi-layer 2D tensor including:
- Object maps (walls, shelves, products).
- Step count and timestep budget (to control trip length).
- A binary mask of unvisited cells.
- Conditional basket (intended purchases) and checkout location.
Actions: Move forward, turn left, turn right, and pickup/checkout.
Reward: Based on the accuracy of items picked up, correct checkout usage, and adherence to the timestep budget. A bonus reward is granted for visiting unique states to further encourage exploration.

2.3 Baselines

The RL approach is compared against:

TSP: Computes the shortest possible route.
PNN: Selects the next product probabilistically based on distance (nearer items are more likely).

3. Key Contributions and Experimental Results

The study evaluates the framework through three stages: trajectory similarity, shelf traffic estimation, and impulse rate/profit optimization.

3.1 Trajectory Generation Accuracy

Using Jensen-Shannon Divergence (JSD) and Wasserstein Distance (WD) to compare simulated trajectories against ground-truth human data:

Results: RL significantly outperformed both TSP and PNN.
- Average JSD: RL (0.476) < PNN (0.676) < TSP (0.777).
- Average WD: RL (0.00920) < PNN (0.0142) < TSP (0.0176).
Qualitative Insight: TSP fails to capture multimodal behaviors (e.g., customers taking longer routes through the bottom of the store). PNN captures some stochasticity but still biases toward shortest paths. MaxEnt RL successfully recovers diverse, valid trajectories that align with human behavior.

3.2 Estimating Shelf Traffic Density

Shelf traffic density ( $\theta_b$ ) is the probability a shelf is visited.

Method: Trajectories were generated to mark visited shelves.
Results: RL-generated traffic density maps were closer to human ground truth (lower JSD/WD) than TSP or PNN. Heuristics failed to predict visits to shelves that were not on the direct shortest path between essential items and checkout.

3.3 Estimating Impulse Rates

Impulse rates were estimated using the formula: $P_{purchase} = P_{visit\_shelf} \times P_{impulse\_rate}$ .

Challenge: For certain product clusters (e.g., Cluster 2), TSP and PNN trajectories never visited the shelves containing impulse items (Soft Drinks, Fruits/Yogurt), leading to division-by-zero errors or infinite impulse rate estimates.
RL Performance: RL trajectories successfully visited these shelves. While absolute values differed slightly from ground truth, RL preserved the relative ordering of impulse rates (correctly identifying Soft Drinks as more impulsive than Fruits/Yogurt), whereas heuristics failed to distinguish them.

3.4 Layout Optimization (Repositioning)

The authors simulated repositioning a single impulse product to an unoccupied, high-traffic shelf to maximize profit.

Decision Making: Only RL identified the correct "most profitable" impulse product (Soft Drinks) and the correct high-traffic shelf locations, matching the decisions derived from actual human data. TSP and PNN selected suboptimal products and locations.
Profit Outcome: When evaluated with human trajectories, the RL-informed layout yielded a profit gain ($0.162) comparable to the ground-truth optimal layout. Layouts based on TSP and PNN yielded significantly lower returns ($0.090 and $0.050, respectively).

4. Significance and Claims

The paper claims that Maximum Entropy RL provides a practical, behaviorally grounded alternative to both oversimplified heuristics and data-intensive approaches.

Bridging the Gap: RL fills the void between the inaccuracy of TSP/PNN and the cost of real data collection.
Actionable Insights: Unlike heuristics, RL-based predictions yield repositioning decisions that align with actual customer behavior, resulting in comparable profit gains to those derived from ground-truth data.
Accessibility: By releasing source code and a digital twin environment, the authors aim to make accurate layout optimization accessible to retailers who cannot afford proprietary data collection.
Limitations & Future Work: The authors acknowledge that training robust RL policies is computationally expensive and currently requires retraining for new layouts. They suggest future work in domain randomization (to generalize across layouts without retraining) and end-to-end layout optimization where an outer agent adjusts placements while an inner agent models behavior.

In conclusion, the study demonstrates that RL-generated trajectories are not just statistically closer to human behavior but are functionally superior for driving profit-maximizing store layout decisions.