Reward Imputation for Policy Optimization

22 concepts13 papers1 proposal

In standard reinforcement learning and multi-armed bandits, an agent learns by interacting with an environment and receiving feedback. However, this feedback loop is often fundamentally constrained by partial observability. In a contextual bandit setting, you only observe the reward for the specific action you chose; the outcomes of all alternative actions remain completely hidden. In real-world deployments like traffic signal control or healthcare monitoring, this problem is exacerbated by physical constraints: sensors fail, data goes missing, or counterfactual outcomes are inherently unobservable.

The Pitfalls of Naive Solutions

When faced with missing or unobserved rewards, a common engineering instinct is to fill the gaps with zeros (zero-padding) or simply discard the incomplete data points. However, as Hanyang Chen et al. demonstrate, zero-padding introduces a severe mathematical ambiguity. The optimization algorithm cannot distinguish between an action that genuinely yielded a terrible, low-performance outcome and an action whose reward sensor was simply offline.

This ambiguity biases the learned policy. As explored by Simone Parisi et al. in the context of Monitored Markov Decision Processes, if an agent assumes unmonitored actions yield zero reward, it develops deceptive or highly suboptimal behaviors, actively avoiding paths that might be highly beneficial but lack active monitoring.

Simulating Full Information via Imputation

The core insight of this research direction is to treat unobserved rewards not as zeros, but as missing data to be statistically imputed. By leveraging a predictive model trained on the observed feedback, we can generate synthetic or "fictitious" rewards for the unchosen actions or missing sensors.

Why does this work? It fundamentally changes the optimization landscape. Instead of optimizing over a sparse, high-variance partial-information space, reward imputation constructs a pseudo-"full-information" environment.

Xiao Zhang et al. and Ninglu Shao et al. show that incorporating these model-based estimates into a batched bandit framework acts as a powerful regularizer. By formulating the problem as an imputation-regularized ridge regression, the agent uses its own internal predictions to smooth out the objective function. This full-information signal drastically accelerates model convergence and reduces variance compared to learning solely from sparse, executed actions.

Similarly, Minmin Chen et al. demonstrate that filling these missing data gaps allows the application of convex surrogate objectives that are mathematically calibrated. This guarantees that minimizing the easier, imputed loss function leads directly to the true optimal policy. This concept of using fictitious rewards to guide learning when true rewards are unobserved traces back to foundational work in repeated games by Nahum Shimkin et al., who used artificial proxies to update strategies based on deviations from a target envelope.

Stabilizing Offline and Counterfactual Learning

This mechanism is equally potent in offline settings, where we must evaluate or learn a policy entirely from historical logs. In fields like healthcare, we cannot test new policies online due to safety risks, yet historical logs only contain the actions chosen by human practitioners.

To solve this, Gi-Soo Kim et al. use counterfactual imputation to estimate outcomes for the actions not taken in historical records. This populates a complete reward matrix, transforming a static offline dataset into a simulated interactive environment where a bandit algorithm can safely learn. When human expert annotations of these counterfactuals are available but incomplete, Shengpu Tang et al. show that predictive models can fill in the missing expert feedback, stabilizing the importance sampling estimators used for policy evaluation.

Managing Uncertainty and Exploration

If we are using a model to guess missing rewards, how do we prevent the agent from getting trapped by its own incorrect guesses? The answer lies in how the imputation handles uncertainty.

In online settings where exploration is critical, we cannot just impute the mean expected reward. Yikun Ban et al. show that when component-level feedback is missing in multi-part decision tasks, substituting the missing sub-rewards with optimistic estimates derived from Upper Confidence Bound (UCB) calculations preserves the exploration-exploitation trade-off. This allows the system to explore complex dependencies without requiring granular ground-truth labels for every single sub-component.

Furthermore, when data missingness is structured—such as being Missing at Random (MAR)—Ilia Mahrooghi et al. demonstrate that algorithms can leverage auxiliary variables, or "mediators," to refine reward estimations and tighten confidence bounds, achieving near-optimal regret even under imperfect monitoring.

Conclusion

Whether dealing with missing sensor data in urban infrastructure (Hao Mei et al.), delayed future reward components (Giulia Romano et al.), or unselected candidate models (Parnian Kassraie et al.), the underlying principle remains identical. By replacing missing feedback with structured, model-based synthetic rewards—whether regularized, optimistic, or counterfactual—we bridge the gap between theoretical full-feedback scenarios and the messy, partial-information realities of practical deployment.

Key Foundational Work

Surrogate Objectives for Batch Policy Optimization in One-step Decision Making (2019) — contributed 1 concept elements to this direction.
On-Line Learning with Imperfect Monitoring (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_synthetic_feedback_generation_673a9a8f,
  title = {synthetic feedback generation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/synthetic-feedback-generation/rdr_673a9a8f25cc46a4996489d8af43aa32},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_synthetic_feedback_generation_673a9a8f_v1,
  title = {synthetic feedback generation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/synthetic-feedback-generation/rdr_673a9a8f25cc46a4996489d8af43aa32/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake