Online Decision-Focused Learning

This paper introduces the first provably convergent online algorithms for decision-focused learning in dynamic environments by regularizing non-differentiable objectives and employing perturbation techniques to handle non-convexity, thereby establishing static and dynamic regret bounds and demonstrating superior performance over standard benchmarks.

The Gist

Here is an explanation of the paper "Online Decision-Focused Learning" using simple language, analogies, and metaphors.

The Big Picture: The "Perfect Chef" Problem

Imagine you are a chef running a restaurant. Your goal isn't just to guess the weather correctly; your goal is to cook a meal that sells well based on the weather.

• The Old Way (Prediction-Focused): You hire a meteorologist. Their only job is to predict the temperature as accurately as possible. If they predict 75°F when it's actually 76°F, they get a "bad grade" because they were wrong. But maybe that 1-degree error makes you cook a soup instead of a salad, and the customers hate it. The meteorologist doesn't care about the soup; they only care about the temperature number.
• The New Way (Decision-Focused): You hire a "Smart Chef." They don't just try to guess the temperature perfectly. They try to guess the temperature in a way that leads to the best menu. If predicting 76°F leads to a better salad than predicting 75°F, the Smart Chef will intentionally predict 76°F, even if the real temperature is 75°F. They optimize for the result, not the accuracy.

The Problem: The "Moving Target"

Most research on this "Smart Chef" idea assumes the restaurant is static. The menu doesn't change, the customers are the same, and the weather patterns are predictable. You can cook a big batch of data, train the chef, and then serve forever.

But the real world is messy.

• The customers change their minds every day.
• The weather patterns shift unpredictably.
• New ingredients appear and old ones disappear.

This is the Online setting. The chef has to make a decision right now, learn from the result, and immediately adjust for the next day, all while the rules of the game are changing.

The Two Big Hurdles

The authors of this paper say, "Okay, let's make a Smart Chef for a moving target," but they hit two massive walls:

1. The "Stuck" Wall (Non-Differentiability):
   Imagine the chef's decision is a light switch. It's either "On" (Salad) or "Off" (Soup). There is no "half-on." In math, you can't take a smooth step (a gradient) to figure out how to improve a switch; you just snap it. Standard learning algorithms need smooth slopes to slide down to a better solution. If the slope is a cliff or a flat floor, the algorithm gets stuck.

   • The Fix: The authors put "cushioning" (regularization) under the switch. Instead of a hard snap, the decision becomes a dimmer switch that can slide smoothly. This allows the algorithm to "feel" the slope and learn.

2. The "Labyrinth" Wall (Non-Convexity):
   Imagine the chef is trying to find the lowest point in a mountain range to minimize costs. But the mountain isn't a smooth bowl; it's a jagged landscape full of valleys, peaks, and holes. If you just walk downhill, you might get stuck in a small, shallow valley (a local minimum) and think you've found the bottom, when there's a much deeper valley nearby.

   • The Fix: They use a "Near-Optimal Oracle." Think of this as a magical compass that doesn't promise to find the absolute deepest valley, but guarantees to find a valley that is "good enough" (close to the best). They combine this compass with random "shakes" (perturbations) to help the chef jump out of shallow valleys and keep searching.

The Two New Algorithms

The paper proposes two specific recipes (algorithms) for this Smart Chef:

1. DF-FTPL (The "Memory Keeper")

• How it works: This algorithm looks at the entire history of the restaurant. It says, "Based on everything that happened from Day 1 to today, plus a little bit of random noise to keep things interesting, what is the best strategy?"
• Best for: Environments that change slowly. It's great at finding a solid, stable strategy that works well on average over time.
• The Metaphor: It's like a seasoned manager who keeps a massive ledger of every mistake and success, then uses that history to make a slightly randomized decision to avoid getting stuck in old habits.

2. DF-OGD (The "Adaptive Sprinter")

• How it works: This algorithm doesn't care as much about the distant past. It focuses on the most recent feedback. It takes a small step in the direction that seemed best just moments ago, then immediately adjusts.
• Best for: Environments that change fast. If the customers' tastes flip-flop every hour, this algorithm is agile enough to keep up.
• The Metaphor: It's like a surfer. They don't plan the whole ocean; they just react to the very next wave, adjusting their balance constantly to stay on top.

The Results: Why It Matters

The authors tested these algorithms on a classic puzzle called the Knapsack Problem (packing a bag with the most valuable items without exceeding the weight limit).

• The Competition: They compared their "Smart Chefs" against:
  1. The Traditional Chef: Who just tries to predict item values perfectly (Prediction-Focused).
  2. The "Smart" Chef (Old Version): Who tries to optimize decisions but wasn't built for a moving target.
• The Outcome: The new algorithms (DF-FTPL and DF-OGD) won. They made better decisions and lost less money, even when the data was messy and changing. Crucially, they proved mathematically that they would eventually get better and better, even in this chaotic environment.

Summary in One Sentence

This paper teaches computers how to make decisions (not just predictions) in a changing world by smoothing out the math so they can learn, and using smart shortcuts to avoid getting stuck in bad solutions.

Technical Summary

Here is a detailed technical summary of the paper "Online Decision-Focused Learning" published at ICLR 2026.

1. Problem Definition

The paper addresses the extension of Decision-Focused Learning (DFL) from static, batch settings to dynamic, online environments.

• Context: In many real-world applications (e.g., supply chain, revenue management), decisions are made based on predictions. Traditional "predict-then-optimize" approaches train models to minimize prediction error (e.g., MSE), which often leads to suboptimal downstream decisions because small prediction errors can be amplified by the optimization process.
• DFL Paradigm: DFL trains the predictive model to directly minimize the loss associated with the downstream decision. This is a bi-level optimization problem:
  • Inner Problem: Given a predicted cost vector, solve a linear optimization problem over a convex polytope $W$ to find the optimal decision $w^*_t$.
  • Outer Problem: Update the prediction model parameters $\theta$ to minimize the actual cost incurred by the decision $w^*_t$.
• The Challenge (Online Setting): The paper investigates a setting where data arrives sequentially ($t=1 \dots T$), and both the data distribution and the objective function evolve over time (non-stationary).
  • Non-differentiability: The inner optimization problem (minimizing a linear function over a polytope) yields a solution $w^*_t(\theta)$ that is piecewise constant (a vertex of the polytope). Consequently, the mapping $\theta \mapsto w^*_t(\theta)$ is not differentiable, and the outer objective function has zero or undefined gradients.
  • Non-convexity: The resulting loss function is generally non-convex.
  • Regret: The goal is to minimize Static Regret (compared to the best fixed parameter $\theta$) and Dynamic Regret (compared to a sequence of time-varying optimal parameters), which is significantly harder in non-stationary environments.

2. Methodology

To overcome the non-differentiability and non-convexity, the authors propose a framework combining regularization and perturbation techniques with approximate oracles.

A. Regularization for Differentiability

Since the true decision $w^*_t(\theta)$ is non-differentiable, the authors introduce a regularized surrogate decision $\tilde{w}_t(\theta)$:
$$\tilde{w}_t(\theta) \in \arg\min_{w \in W} \{ \langle g(\theta, X_t), w \rangle + \alpha_t R(w) \}$$

• Regularizer $R$:
  • For general polytopes, they use a log-barrier function to keep the solution in the strict interior of $W$, ensuring differentiability via the Implicit Function Theorem.
  • For the simplex (e.g., knapsack with item selection), they use negative entropy, which results in a Softmax mapping.
• Surrogate Loss: The algorithm minimizes $\tilde{f}_t(\theta) = \langle \bar{g}_t(X_t), \tilde{w}_t(\theta) \rangle$, which is differentiable and Lipschitz continuous.

B. Handling Non-Convexity

Even with regularization, the surrogate loss $\tilde{f}_t$ is non-convex. The authors assume access to an $\xi$-approximate offline optimization oracle ($O_\xi$).

• This oracle returns a parameter $\vartheta$ such that $f(\vartheta) \leq \inf f(\theta) + \xi$.
• This reflects practical reality where finding a global minimum in non-convex landscapes is impossible, but local minima (found via SGD) are sufficient.

C. Proposed Algorithms

The paper introduces two algorithms tailored to different regret metrics:

1. DF-FTPL (Decision-Focused Follow-the-Perturbed-Leader):

   • Mechanism: At each step, it minimizes the cumulative sum of regularized losses plus a random perturbation (exponential noise).
   • Update: $\theta_{t+1} = O_\xi \left( \sum_{i=1}^t \tilde{f}_i - \langle \sigma_t, \cdot \rangle \right)$.
   • Goal: Achieves Static Regret bounds. The perturbation smooths the non-convex landscape, allowing the algorithm to escape local minima and track the best static strategy.

2. DF-OGD (Decision-Focused Online Gradient Descent):

   • Mechanism: A variant of Online Gradient Descent adapted for non-convex, bi-level problems.
   • Update: Instead of minimizing cumulative loss, it uses the gradient of the current surrogate loss evaluated at a random point between the current parameter and the oracle's output.
   • Update: $\theta_{t+1} = \Pi_\Theta (\theta_t - \eta_t \tilde{\nabla}_t(u_t))$, where $u_t$ is a random interpolation.
   • Goal: Achieves Dynamic Regret bounds. It adapts to changing environments by using time-varying step sizes and regularization parameters.

3. Key Contributions

1. Theoretical Foundation: The first provable regret bounds for Online Decision-Focused Learning. Previous work was limited to batch settings.
2. Novel Algorithms: Development of DF-FTPL and DF-OGD, specifically designed to handle the bi-level, non-differentiable, and non-convex nature of DFL in dynamic settings.
3. Regret Guarantees:
   • DF-FTPL: Establishes a static regret bound of $\tilde{O}(T^{-1/4})$ (assuming the oracle error $\xi$ scales appropriately).
   • DF-OGD: Establishes a dynamic regret bound of $\tilde{O}((1+P_T)^{1/4}T^{-1/4})$, where $P_T$ measures the path length (variability) of the optimal solutions over time.
   • Dimensionality: The bounds are largely independent of the decision space dimension $d$ (depending only on $\ln \ln d$), making them suitable for high-dimensional decision problems.
4. Assumption Analysis: Introduction of a margin assumption (H2) regarding the cost function to bound the distance between the true optimal decision and the regularized surrogate.

4. Experimental Results

The authors evaluated their algorithms on a Knapsack problem (inspired by Mandi et al., 2024) with synthetic, non-stationary data.

• Baselines: Compared against Prediction-Focused Learning (PF-OGD) (minimizing MSE) and Online Smart Predict-then-Optimize (Online SPO).
• Findings:
  • Decision Performance: Both DF-FTPL and DF-OGD significantly outperformed the baselines in terms of cumulative decision cost (the actual metric of interest).
  • Prediction Performance: Interestingly, the DFL methods incurred higher prediction error (MSE) than PF-OGD. This confirms the core DFL hypothesis: minimizing prediction error does not guarantee optimal decisions, especially when the model is misspecified or the environment is non-stationary.
  • Robustness: The algorithms remained effective even in high-dimensional settings (tested with $K=80$ items).

5. Significance

• Bridging Theory and Practice: This work bridges the gap between the theoretical success of DFL in static settings and the practical necessity of handling non-stationary, online data streams.
• Solving the Gradient Problem: It provides a rigorous mathematical solution to the "zero-gradient" problem inherent in discrete optimization, using regularization and perturbation to enable gradient-based learning.
• Dynamic Adaptation: By establishing dynamic regret bounds, the paper proves that DFL can adapt to shifting environments, a critical requirement for real-world applications like dynamic pricing or resource allocation.
• Future Directions: The authors suggest that while current rates are $O(T^{-1/4})$, faster rates might be achievable with different discretization techniques, and the framework could be extended to more general convex sets using alternative smoothing techniques (e.g., Moreau-Yosida).

In summary, this paper establishes the theoretical and algorithmic groundwork for training predictive models that are robust to uncertainty and capable of adapting to changing environments, prioritizing decision quality over raw prediction accuracy.