Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback".

Jane: The gist:

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we're looking at this paper now, "Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback". It tackles how to train predictive models by focusing on the quality of the decisions they actually make instead of just being right about a prediction.

Jane: It seems like the main gap they are filling is that most existing decision-focused learning methods assume you have all the data upfront and see every single cost vector, but this paper looks at sequential optimization problems where you only get partial feedback based on what you choose to do.

Lu: Exactly. They develop an on-policy learning method specifically for sequential contextual linear optimization under partial feedback, which is a setting they say isn't systematically captured by any existing framework yet.

Meng: So they propose a policy that learns to sample a cost-vector prediction from some conditional distribution and then immediately solves the resulting linear optimization problem based on that prediction. That sounds like it has real potential for online decision making where you can't wait for all the data.

Lalam: And to update this model of predictions, they introduce a two-component hybrid gradient estimator. The first part is a score function estimator, which gives an unbiased but potentially high-variance policy gradient estimate.

Tom: High variance is always a concern when you're dealing with online learning signals, but the second component seems like it's designed to help with that by using a decision-focused plug-in component. This part uses an auxiliary estimate of the latent cost vector to exploit the structure of the downstream optimization problem.

Jane: So they have this two-part update mechanism: one that gives you a clean but noisy signal, and another one that tries to make sense of the cost vector using some other guess, which gets better as that guess improves.

Lu: The analysis shows they achieve an O(T-one/two) bound on the average squared policy-gradient norm for this hybrid update, which matches the standard non-convex stochastic gradient descent rate. That's a solid theoretical baseline for convergence.

Meng: An O(T-one/two) rate is good because it means the learning process converges at a known speed, similar to what you see in standard SGD settings when you don't have all the data at once. But what about actual deployment?

Tom: The experiments on top-k selection, shortest path, combinatorial pricing, and even a real-data energy-scheduling benchmark show that this hybrid gradient approach under bandit feedback achieves lower mean cumulative regret than the contextual-bandit baselines across all four benchmarks.

Jane: And even compared to linear Thompson sampling on three of those benchmarks, it performs better when you're only seeing partial feedback. That suggests this method is robust and useful in real-world online scenarios where you don't have perfect information about the true cost vector.

Lu: Plus, they show that this framework works even with richer conditional generative cost models for the plug-in component, which expands its applicability beyond just simple linear models.

Meng: From a deployment standpoint, it sounds like this isn't just an academic exercise; it’s designed to handle the messiness of real online data where you only get partial feedback from your choices.

Lalam: The paper concludes that this hybrid update couples an unbiased score function update with a decision-focused plug-in update, and under the stated assumptions, its fixed-weight update reaches first-order stationarity at rate O(T-one/two).

Tom: So in simple terms, the authors are showing that by combining a standard gradient estimate with one tailored to exploit how decisions affect future costs, you get a solid convergence guarantee.

Jane: The real implication here is that this method provides more flexibility than some other approaches; it doesn't require you to have a closed-form posterior or an enumerable feasible set, just a distributional cost model and a linear optimization oracle.

Lu: It also suggests that the hybrid gradient is conditionally biased, but only through the nuisance error, which means they are exploring how that bias might improve performance if you adjust those learning parameters over time.

Meng: If you're deploying this in production, knowing it can handle partial feedback better than pure bandit baselines on all those benchmarks is a strong signal about its practical utility.

Lalam: The final results show that semi-bandit and full-information feedback lower regret relative to pure bandit feedback on all four problems, which shows the method's flexibility across different feedback settings.

Tom: It's clear that this paper is focused on building a tool that works in the messy, partial-feedback world of sequential optimization, moving beyond just having accurate predictions to actually making good decisions under uncertainty.

Conclusion: Jane: So, to wrap up, this paper is about training AI models to make better decisions in online optimization problems when you don't get all your data at once—partial feedback.

Tom: Right, so it’s about Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback. The authors are focusing on how to optimize the decision quality itself rather than just getting a prediction score right.

Lu: They introduce a method where you sample a cost vector prediction and then solve the optimization problem based on that, which is different from standard methods that wait for full information.

Jane: And they do this using this two-part gradient estimator—one part being the standard score function and another one being decision-focused plug-in to help exploit the structure of the linear optimization.

Tom: The key result is that under bandit feedback, this hybrid approach beats contextual bandit baselines on all four benchmarks, and even linear Thompson sampling on three of them. That's a solid comparison with concrete numbers there.

Meng: I’m interested in what they say about the regret bound, because for me at scale, we need to know the convergence speed. They show that the average squared policy-gradient norm is bounded by O(T negative one over two), which matches standard non-convex SGD rates.

Lalam: That rate means their fixed-weight update reaches first-order stationarity in that time frame, which is a strong theoretical guarantee for sequential learning under these conditions.

Jane: So, what does this mean practically? It suggests we can get better performance in real online scheduling or pathfinding when the feedback is incomplete, and this method offers flexibility with different types of cost models.

Tom: It means we don't necessarily need a perfect posterior distribution to do good work; we just need a distributional model that allows us to estimate those gradients effectively.

Lu: The implication is that this framework can be extended beyond linear feedback and risk-neutral objectives, which opens the door for more complex real-world problems.

Jane: That sounds like it could help us build more robust AI systems for environments where data collection is expensive or slow to get. What happens when we move from linear optimization to something non-linear?