Adaptive Double-Booking Strategy for Outpatient Scheduling Using Multi-Objective Reinforcement Learning

This paper proposes an adaptive outpatient scheduling framework that integrates individualized no-show predictions with a novel multi-policy reinforcement learning approach, utilizing a KL-divergence-based knowledge transfer mechanism to dynamically optimize booking decisions and balance competing objectives like patient wait times and clinic productivity.

The Gist

Imagine a busy doctor's office as a high-stakes theater production.

Every day, the theater has a fixed number of seats (appointment slots). The goal is to have exactly one person in every seat for every show. However, there's a problem: ghosts.

In this analogy, "ghosts" are patients who book a seat but never show up (no-shows). When a ghost takes a seat, the theater runs empty, the actors (doctors) sit idle, and the show is less profitable. But if the theater tries to fill those empty seats by inviting extra people, they risk a crowded aisle: two real people showing up for the same seat, causing chaos, long waits, and angry audience members.

For years, theater managers (clinic schedulers) have used two main strategies:

1. The "Empty Seat" Rule: Only invite one person per seat. (Safe, but often leaves seats empty).
2. The "Double-Book" Rule: Invite two people for every seat, hoping one will be a ghost. (Risky; sometimes you get two ghosts, sometimes you get two real people and a traffic jam).

The problem with old methods is that they use a one-size-fits-all approach. They treat every patient the same, regardless of whether they are a "reliable attendee" or a "frequent ghost."

The New Solution: The "Smart Conductor"

This paper introduces a new system called Adaptive Double-Booking, powered by Artificial Intelligence (AI). Think of this AI as a Smart Conductor who doesn't just follow a script but learns from the orchestra in real-time.

Here is how it works, broken down into simple steps:

1. The Crystal Ball (Predicting the Ghosts)

Before the Conductor decides who to invite, it uses a special tool (a machine learning model called MHASRF) to look at each patient's history.

• Analogy: It's like checking a weather forecast. If a patient has a history of missing appointments (like a stormy day), the Conductor knows there's a high chance of a "ghost." If they are usually reliable (sunny day), the risk is low.

2. The Three Choices

When a new patient calls to book a ticket, the Conductor has three options:

• Single-Book: Invite one person. (Best for reliable patients).
• Double-Book: Invite two people for the same slot. (Best for "ghost-prone" patients).
• Reject: Say "no" if the schedule is too full.

3. The "Gym" Training (Reinforcement Learning)

How does the Conductor learn the best strategy? It doesn't read a manual. It goes to a simulation gym.

• The AI plays the game thousands of times against a computer simulation of the clinic.
• It tries different strategies: "What if I double-book everyone?" "What if I only double-book on Tuesdays?"
• It gets points for filling seats without causing traffic jams. It gets penalties for empty seats or overcrowding.
• Over time, it learns the perfect balance, just like a video game character leveling up.

4. The "Team of Specialists" (Multi-Objective Learning)

Real life is tricky. Sometimes the clinic wants to maximize profit (fill every seat), and other times they want to minimize stress (avoid overcrowding).

• Instead of training one AI to do everything, this paper trains a team of 10 different AIs.
• Each AI has a slightly different personality. One is a "Profit Maximizer," another is a "Stress Avoider," and another is a "Balancer."
• They talk to each other and share tips (a process called Co-Evolution), helping each other get smarter without losing their unique styles. This gives the clinic a menu of strategies to choose from depending on the day's mood.

5. The "Why" Explainer (SHAP)

One of the coolest parts is that the AI doesn't just make decisions; it explains them.

• Analogy: If you ask the Conductor, "Why did you double-book that slot?" it can point to the data and say, "Because this patient missed 3 appointments last year, and the slot is currently empty."
• This transparency builds trust, so human schedulers know the AI isn't just guessing.

The Results: A Better Show

When the researchers tested this "Smart Conductor" against the old rules:

• Old Rules: Often left seats empty or created traffic jams.
• The Smart Conductor: Found the "Goldilocks" zone. It filled more seats (better efficiency) while keeping the traffic jams to a minimum (better service).

The Big Takeaway

This paper shows that we don't need to choose between an empty clinic and a chaotic one. By using AI to predict who is likely to be a "ghost" and when to double-book, clinics can run smoother, doctors can stay on schedule, and patients get the care they need without the headache of long waits.

It's like moving from a rigid, manual ticketing system to a dynamic, smart system that knows exactly how many people to invite to the party to ensure everyone has a seat, but no one is standing in the hallway.

Technical Summary

1. Problem Statement

Outpatient clinics face significant operational inefficiencies due to patient no-shows (missed appointments without prior cancellation). These disruptions lead to wasted physician capacity, reduced productivity, and delayed care. To mitigate this, clinics often employ overbooking or double-booking (assigning two patients to a single time slot). However, static or poorly calibrated policies often result in overcrowding, extended waiting times, and reduced service quality when actual attendance exceeds expectations.

Key Challenges Identified:

• Static Policies: Existing methods rely on fixed heuristics (e.g., double-book if no-show risk > 50%) that fail to adapt to real-time booking sequences or evolving system states.
• Lack of Individualization: Most strategies do not incorporate patient-specific no-show probabilities into the decision-making process.
• Multi-Objective Conflict: Clinics must balance three competing objectives:
  1. Maximizing effective slot utilization (avoiding empty slots).
  2. Minimizing double-show risk (avoiding two patients arriving for one slot).
  3. Maintaining attendance balance (aligning expected attendance with the single-patient capacity).
• Limitations of Traditional Optimization: Stochastic programming and heuristics struggle with the sequential, uncertain nature of rolling booking requests over multi-day horizons.

2. Methodology

The authors propose a unified framework integrating individualized no-show prediction with Multi-Objective Reinforcement Learning (MO-RL).

A. No-Show Prediction Layer

• Model: Uses a Multi-Head Attention Soft Random Forest (MHASRF) model.
• Function: Predicts individualized no-show probabilities ($\pi_i$) for each patient based on demographics, appointment context, lead time, and historical behavior.
• Role: These probabilities serve as critical inputs to the RL state representation, enabling context-aware decisions.

B. Markov Decision Process (MDP) Formulation

The scheduling problem is modeled as an MDP with the following components:

• State ($s_t$): Includes clinic/physician context, current slot status (available, single-booked, double-booked), remaining capacity, and the predicted no-show probability ($\pi_i$) of the incoming patient.
• Action ($a_t$): The agent chooses one of three actions:
  1. Single-book: Assign one patient to the slot.
  2. Double-book: Assign two patients to the slot.
  3. Reject: Decline the request if no feasible slots exist.
• Reward Function: A multi-objective reward ($R_t$) combining:
  • Effective Slot Utilization ($U_t$): Reward for exactly one patient attending.
  • Double-Show Avoidance ($D_t$): Penalty for two patients attending a double-booked slot.
  • Attendance Balance ($B_t$): Reward for aligning expected attendance with the target of one patient per slot.
• Reward Shaping: To address delayed feedback (outcomes are only known on the appointment day), the authors use shaped rewards based on expected attendance derived from $\pi_i$ to accelerate training.

C. Reinforcement Learning Algorithm: MPPPO with MPCEM

• Base Algorithm: Multi-Policy Proximal Policy Optimization (MPPPO). Instead of training a single policy, the system trains a set of policies ($\Pi$) in parallel, each optimized with a different weight vector ($\alpha, \beta, \gamma$) for the three objectives. This approximates the Pareto frontier, allowing clinics to select a policy based on current operational priorities.
• Innovation: Multi-Policy Co-Evolution Mechanism (MPCEM):
  • To prevent policies from getting stuck in local optima and to improve convergence, the authors introduce a mechanism for knowledge transfer between policies.
  • Novel $\tau$ Rule: Unlike fixed transfer rates, this study proposes a KL-divergence-based adaptive $\tau$. The degree of parameter sharing between neighboring policies is modulated by their behavioral similarity (measured via Kullback-Leibler divergence).
  • Benefit: Stronger knowledge transfer occurs between behaviorally similar policies, while diversity is preserved among dissimilar ones.

D. Interpretability

• SHAP (SHapley Additive exPlanations): Used to interpret both the no-show predictions and the RL agent's scheduling decisions, ensuring the model's logic aligns with clinical intuition.

3. Key Contributions

1. First Multi-Objective MDP for Double-Booking: Formulates outpatient scheduling as an MDP that explicitly models single-book, double-book, and reject decisions while restricting slots to a maximum of two patients.
2. Integration of Predictive Analytics: Directly embeds individualized no-show probabilities (from MHASRF) into the RL state, moving beyond population-level averages.
3. Adaptive Multi-Policy Framework: Implements MPPPO with a novel KL-based adaptive $\tau$ mechanism for co-evolution, improving training stability and the diversity of trade-offs in the Pareto frontier.
4. Data-Driven Decision Support: Provides a dynamic alternative to fixed heuristics, capable of adapting to real-time booking conditions and patient risk profiles.

4. Experimental Results

The framework was tested using a dataset of 157,494 appointment records from a large Middle Eastern healthcare provider (101,532 records after cleaning). A custom OpenAI Gym environment simulated a 14-day planning horizon.

• Performance vs. Baselines: The MPPPO policies consistently outperformed both Single-Booking (SB) and Fixed Double-Booking (DB) baselines (using thresholds of 0.5–0.9).
  • Effective Slot Utilization: MPPPO achieved 0.762–0.793, compared to 0.642 (SB) and 0.678–0.706 (Fixed DB).
  • Average Weighted Reward: MPPPO policies achieved rewards up to 8,992.2, significantly higher than the best fixed DB baseline (8,058.1).
• Trade-off Analysis:
  • Policies emphasizing Attendance Balance (e.g., MPPPO 3) achieved the best overall performance, suggesting that balancing expected attendance is a strong surrogate for optimizing both utilization and congestion.
  • MPPPO 3 and MPPPO 10 formed an approximate Pareto front, offering optimal trade-offs between utilization and double-show avoidance.
• Robustness: The system remained robust to moderate prediction errors ($\pm3\%$ perturbation in no-show probabilities), with reward changes generally below 1%. However, significant overestimation of no-show risk ($\pm5\%$) led to performance degradation due to overly aggressive double-booking.
• Interpretability (SHAP):
  • Single-booking was favored when no-show risk was low and workload was high.
  • Double-booking was driven primarily by high predicted no-show risk and available slot flexibility, confirming the model learned intuitive, operationally sound strategies.

5. Significance and Conclusion

This research presents a significant advancement in healthcare operations management by shifting from static, rule-based overbooking to adaptive, data-driven scheduling.

• Operational Impact: The framework allows clinics to dynamically adjust booking strategies based on real-time demand and specific patient risk profiles, maximizing resource utilization without compromising service quality.
• Methodological Impact: The introduction of the KL-based adaptive $\tau$ in multi-policy RL offers a new approach to stabilizing training and exploring trade-offs in complex, multi-objective environments.
• Practical Utility: By providing a set of Pareto-optimal policies, the system empowers clinic managers to select a scheduling strategy that aligns with their specific operational goals (e.g., prioritizing efficiency vs. minimizing wait times) and adapt to changing conditions.

The study concludes that integrating predictive analytics with multi-objective reinforcement learning creates a resilient, interpretable, and highly effective solution for managing outpatient appointment scheduling under uncertainty.