# Hindsight Learning for MDPs with Exogenous Inputs

arXiv: https://arxiv.org/abs/2207.06272 · HTML: https://mlsanity.com/paper/2207.06272/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 120 references that are in the map.
- First posted on arXiv 13 Jul 2022.

## Builds on (most cited first, 30 of 54)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Learning Scheduling Algorithms for Data Processing Clusters](https://mlsanity.com/paper/1810.01963/) (2018)
- [Reinforcement and Imitation Learning via Interactive No-Regret Learning](https://mlsanity.com/paper/1406.5979/) (2014)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Adversarially Trained Actor Critic for Offline Reinforcement Learning](https://mlsanity.com/paper/2202.02446/) (2022)
- [Training Agents using Upside-Down Reinforcement Learning](https://mlsanity.com/paper/1912.02877/) (2019)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Causal Bandits: Learning Good Interventions via Causal Inference](https://mlsanity.com/paper/1606.03203/) (2016)
- [Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction](https://mlsanity.com/paper/1703.01030/) (2017)
- [Counterfactual Credit Assignment in Model-Free Reinforcement Learning](https://mlsanity.com/paper/2011.09464/) (2020)
- [OR-Gym: A Reinforcement Learning Library for Operations Research Problems](https://mlsanity.com/paper/2008.06319/) (2020)
- [Heuristic-Guided Reinforcement Learning](https://mlsanity.com/paper/2106.02757/) (2021)
- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method](https://mlsanity.com/paper/1708.05930/) (2017)
- [Variance Reduction for Reinforcement Learning in Input-Driven Environments](https://mlsanity.com/paper/1807.02264/) (2018)
- [Universal Trading for Order Execution with Oracle Policy Distillation](https://mlsanity.com/paper/2103.10860/) (2021)
- [Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information](https://mlsanity.com/paper/2206.04282/) (2022)

## Built on by (most cited first, 26 of 26)

- [On Overcoming Miscalibrated Conversational Priors in LLM-based Chatbots](https://mlsanity.com/paper/2406.01633/) (2024)
- [Deep Inventory Management](https://mlsanity.com/paper/2210.03137/) (2022)
- [Learning in POMDPs is Sample-Efficient with Hindsight Observability](https://mlsanity.com/paper/2301.13857/) (2023)
- [Sample Efficient Reinforcement Learning in Mixed Systems through Augmented Samples and Its Applications to Queueing Networks](https://mlsanity.com/paper/2305.16483/) (2023)
- [VC Theory for Inventory Policies](https://mlsanity.com/paper/2404.11509/) (2024)
- [Online Reinforcement Learning in Non-Stationary Context-Driven Environments](https://mlsanity.com/paper/2302.02182/) (2023)
- [Neural Coordination and Capacity Control for Inventory Management](https://mlsanity.com/paper/2410.02817/) (2024)
- [Learning an Inventory Control Policy with General Inventory Arrival Dynamics](https://mlsanity.com/paper/2310.17168/) (2023)
- [Reinforcement Learning with Exogenous States and Rewards](https://mlsanity.com/paper/2303.12957/) (2023)
- [Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observations](https://mlsanity.com/paper/2306.01243/) (2023)
- [Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning](https://mlsanity.com/paper/2409.14557/) (2024)
- [Sequential Decision-Making under Uncertainty: A Robust MDPs review](https://mlsanity.com/paper/2404.00940/) (2024)
- [Multi-Agent Reinforcement Learning with Long-Term Performance Objectives for Service Workforce Optimization](https://mlsanity.com/paper/2503.01069/) (2025)
- [Learning Virtual Machine Scheduling in Cloud Computing through Language Agents](https://mlsanity.com/paper/2505.10117/) (2025)
- [Deep RL Dual Sourcing Inventory Management with Supply and Capacity Risk Awareness](https://mlsanity.com/paper/2507.14446/) (2025)
- [Ready from Day 1: Population-Aware Coordination for Large-Scale Constrained Multi-Agent Systems](https://mlsanity.com/paper/2605.13900/) (2026)
- [Policy Optimization in Hybrid Discrete-Continuous Action Spaces via Mixed Gradients](https://mlsanity.com/paper/2605.14297/) (2026)
- [Minimax PAC Bounds for Learning in Exogenous Contextual MDPs](https://mlsanity.com/paper/2606.25170/) (2026)
- [Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Information](https://mlsanity.com/paper/2306.08762/) (2023)
- [Optimizing Heat Alert Issuance with Reinforcement Learning](https://mlsanity.com/paper/2312.14196/) (2023)
- [Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observation](https://mlsanity.com/paper/2402.18149/) (2024)
- [Online design of dynamic networks](https://mlsanity.com/paper/2410.08875/) (2024)
- [Zero-shot Generalization in Inventory Management: Train, then Estimate and Decide](https://mlsanity.com/paper/2411.00515/) (2024)
- [Scalable Reinforcement Learning for Virtual Machine Scheduling](https://mlsanity.com/paper/2503.00537/) (2025)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)
- [Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?](https://mlsanity.com/paper/2601.20694/) (2026)

## Abstract (arXiv)

Many resource management problems require sequential decision-making under uncertainty, where the only uncertainty affecting the decision outcomes are exogenous variables outside the control of the decision-maker. We model these problems as Exo-MDPs (Markov Decision Processes with Exogenous Inputs) and design a class of data-efficient algorithms for them termed Hindsight Learning (HL). Our HL algorithms achieve data efficiency by leveraging a key insight: having samples of the exogenous variables, past decisions can be revisited in hindsight to infer counterfactual consequences that can accelerate policy improvements. We compare HL against classic baselines in the multi-secretary and airline revenue management problems. We also scale our algorithms to a business-critical cloud resource management problem -- allocating Virtual Machines (VMs) to physical machines, and simulate their performance with real datasets from a large public cloud provider. We find that HL algorithms outperform domain-specific heuristics, as well as state-of-the-art reinforcement learning methods.