Reinforcement Learning for Intensity Control: An Application to Choice-Based Network Revenue Management

This paper proposes a practical continuous-time reinforcement learning framework for intensity control in choice-based network revenue management that leverages event-driven structures to avoid time discretization, demonstrating superior performance and scalability compared to state-of-the-art discretization-based methods.

The Gist

Imagine you are running a busy airline or a hotel chain. You have a limited number of seats or rooms (resources) and a stream of customers arriving randomly throughout the day. Your goal is to decide what to offer to each customer (e.g., "Do we sell them a flight to Paris, or just a flight to London?") to make the most money possible before the day ends.

This is a classic problem called Revenue Management.

The Old Way: The "Stop-Start" Video Game

Traditionally, computers tried to solve this by breaking time into tiny, rigid chunks, like frames in a video game.

• The Problem: Imagine trying to catch a falling apple. If you only check for the apple every second, you might miss it if it falls between checks. If you check every millisecond, you catch it perfectly, but your brain gets so tired from checking so often that you can't think about what to do with the apple.
• The Trade-off:
  • Coarse Grid (Checking every second): Fast to compute, but you miss opportunities and make bad decisions because you aren't watching closely enough.
  • Fine Grid (Checking every millisecond): You see everything, but the computer takes forever to run the numbers, often crashing or getting stuck.
• The Result: For a long time, we had to choose between being fast or being accurate. We couldn't have both.

The New Way: The "Surprise Party" Strategy

This paper introduces a new method using Reinforcement Learning (RL)—a type of AI that learns by trial and error. But instead of checking the clock constantly, the authors realized something brilliant: You only need to make a decision when something actually happens.

Think of it like hosting a surprise party.

• The Old Way: You stand there checking your watch every 5 minutes, asking, "Is anyone here yet?" even if the house is empty. It's exhausting and wasteful.
• The New Way: You sit back and relax. You only react when the doorbell rings (a customer arrives).
  • When the doorbell rings, you look at who is there and decide what to offer them.
  • When the doorbell doesn't ring, nothing changes, so you don't need to do anything.

How It Works (The Magic Trick)

The authors call this "Event-Driven Intensity Control." Here is the simple breakdown:

1. The "Event" is the Key: In their system, the only time the state of the world changes is when a customer arrives. Between arrivals, the inventory (seats/rooms) stays exactly the same.
2. No More "Fake" Time Steps: Because the system only changes at specific moments (the doorbells), the computer doesn't need to simulate the empty time in between. It jumps straight from one customer to the next.
3. Learning on the Fly: The AI learns a strategy (a policy) by watching these "doorbell rings." It asks: "When a customer arrived at 2:00 PM with 5 seats left, did offering the Paris flight make more money than the London flight?" It adjusts its brain based on the answer.

Why This is a Big Deal

The paper tested this new "Doorbell Strategy" against the old "Watch-Checking" methods in three scenarios:

• Small Problems: It learned to make almost perfect decisions, beating the old "best" methods.
• Medium Problems: The old methods got confused and unstable when they tried to check time too frequently. The new method stayed calm and accurate.
• Huge Problems: Imagine a network with 100 resources and 200 products. The old methods would take days or weeks to calculate a solution, or they would give up entirely. The new method handled it like a breeze, finding a near-perfect solution in a reasonable time.

The "Bursty" Bonus:
The paper also tested a scenario where customers suddenly flooded in (like a flash sale).

• The Old Method panicked. To handle the rush, it had to check the clock super fast, which slowed everything down and made it less accurate.
• The New Method didn't care. It just reacted to the doorbells. Whether 1 person or 1,000 people arrived, it only did work when the doorbell rang. It was fast and accurate.

The Bottom Line

This paper is like inventing a smart thermostat that doesn't check the temperature every second. Instead, it only turns the heat on or off when the temperature actually changes.

By realizing that we only need to act when events happen, the authors created an AI that is:

1. Faster: It skips all the boring, empty time.
2. Smarter: It doesn't get confused by the "grid" of time; it sees the real flow of events.
3. Scalable: It can handle massive, complex problems that used to be impossible to solve.

In short, they taught the computer to stop staring at the clock and start listening to the doorbell.

Technical Summary

1. Problem Definition

The paper addresses Intensity Control, a class of continuous-time dynamic optimization problems where the system state evolves via a Poisson arrival process, and decisions (controls) are made to influence the intensity of these arrivals or the resulting state transitions.

• Specific Application: The authors focus on Choice-Based Network Revenue Management (NRM).
  • Context: A firm manages $m$ resources and $n$ products over a continuous time horizon $[0, T]$.
  • Dynamics: Customers arrive according to a Poisson process with rate $\lambda$. Upon arrival, the firm offers an assortment (subset) of products. Customers choose a product or make no purchase based on a choice model (e.g., Multinomial Logit).
  • Objective: Maximize expected total revenue by dynamically selecting assortments.
• Challenges:
  • Curse of Dimensionality: The state space (remaining inventory combinations) and action space (all possible subsets) are exponentially large, making exact Dynamic Programming (DP) infeasible.
  • Continuous Time vs. Discretization: Traditional RL methods require discretizing the time horizon. However, for intensity control, finding the optimal grid size is a trade-off: fine grids reduce approximation error but explode computational costs and cause numerical instability; coarse grids introduce significant performance gaps.
  • Non-Stationarity: In bursty arrival environments, fixed time discretization struggles to capture rapid state changes.

2. Methodology

The authors propose a Continuous-Time Reinforcement Learning (CT-RL) framework that avoids upfront time discretization by leveraging the event-driven nature of the problem.

A. Core Insight: Event-Driven Discretization

Unlike diffusion processes where state changes continuously, intensity control systems have piecewise constant sample paths. The state only changes at customer arrival times (jump times).

• Key Strategy: The algorithm only queries the policy and updates values at these specific jump times ($\tau_l$).
• Adaptive Discretization: Instead of a uniform grid, the time horizon is discretized adaptively based on the actual jump times of each sample path. This allows for the exact computation of integrals required for policy evaluation and gradient estimation, eliminating the approximation errors inherent in fixed-grid methods.

B. Theoretical Framework

1. Entropy-Regularized Objective: The authors formulate the problem using a randomized Markov policy $\pi$ with an entropy bonus to encourage exploration. The value function $J(t, x; \pi)$ includes both expected revenue and an entropy term.
2. Martingale Characterization: They establish a martingale orthogonality condition (Theorem 2) for the value function. This serves as the theoretical foundation for deriving continuous-time Temporal Difference (TD) and Policy Gradient (PG) updates without needing the environment's transition probabilities (model-free).
3. Policy Gradient (PG): They derive a computable representation for the policy gradient (Theorem 3) that relies on the difference in value functions before and after a jump, plus the immediate reward. This formula is evaluated exactly using data collected at jump times.

C. Algorithm Design: Actor-Critic

The authors develop Actor-Critic algorithms combining:

• Critic (Policy Evaluation - PE): Estimates the value function $J(t, x)$.
  • Monte Carlo (MC): Uses a loss function based on the mean-squared value error, solvable via closed-form linear regression when using linear function approximation.
  • Temporal Difference (TD): Uses the martingale orthogonality condition for online learning.
• Actor (Policy Improvement): Updates the policy parameters $\phi$ using the derived policy gradient formula.
• Function Approximation: To handle large state/action spaces, they employ:
  • Linear-Pair: Polynomial basis functions for value and policy.
  • Linear-RO: Restricts the policy to revenue-ordered assortments (reducing action space complexity).
  • 2-NNs: Deep Neural Networks (Actor and Critic) for fully non-linear approximation.

3. Key Contributions

1. Continuous-Time RL Framework: A practical framework for intensity control that operates directly in continuous time, eliminating the need for arbitrary time discretization.
2. Theoretical Justification: A rigorous martingale formalization extending entropy-regularized RL (previously applied to diffusion processes) to discrete-state, event-driven intensity control.
3. Adaptive Discretization Procedure: A novel integration technique that computes integrals exactly over sample paths by using jump times as integration boundaries, significantly reducing approximation error compared to uniform grids.
4. Scalability: Demonstrated ability to solve problems with state spaces of size $10^{100}$ and action spaces of size $2^{200}$ using neural network approximations.

4. Experimental Results

The authors conducted extensive numerical experiments comparing their CT-RL approach against:

• Benchmarks: Greedy, Uniform-Random, CDLP (Deterministic Linear Programming), ADP (Approximate Dynamic Programming with discretization), and Discrete-Time A2C.
• Scenarios: Small networks, medium-sized airline networks, and large-scale networks ($m=100, n=200$).

Key Findings:

• Superior Performance: The CT-RL algorithm consistently outperformed classical heuristics and state-of-the-art non-RL benchmarks (CDLP, ADP). In small networks, it achieved 98.89% of the optimal value (approximated by fine-grid DP).
• Robustness to Discretization: Unlike ADP and discrete-time A2C, whose performance fluctuates wildly or degrades with coarser time steps, the CT-RL performance is stable and independent of grid size.
• Efficiency in Bursty Environments: In a scenario with sudden arrival surges, the CT-RL algorithm significantly outperformed discrete-time A2C (up to 16.64% higher revenue with 2-NNs) while maintaining computational costs comparable to the coarse discrete-time grid. Discrete-time methods required a fine grid (3.5x more time) to approach similar performance.
• Scalability: The 2-NNs approach successfully solved a large-scale problem ($10^{100}$ states) with a performance gap of only 0.13% from the theoretical upper bound (CDLP).

5. Significance

• Theoretical Advancement: This work bridges the gap between continuous-time control theory and modern deep reinforcement learning, providing a principled way to handle continuous time without the "curse of discretization."
• Practical Impact: It offers a viable solution for high-dimensional revenue management problems where exact optimization is impossible and traditional discretization-based RL is either too slow or inaccurate.
• Generalizability: While demonstrated on NRM, the framework is applicable to any event-driven intensity control problem, such as queueing admission control, as shown in the paper's appendix.

In summary, the paper demonstrates that by exploiting the inherent structure of event-driven systems (jump times), one can design RL algorithms that are both more accurate (no discretization error) and more efficient (fewer evaluation points) than traditional discrete-time approaches, particularly in non-stationary and high-dimensional environments.