mlsanityData to 7 Oct 2026

Hindsight Learning for MDPs with Exogenous Inputs

arXiv 2207.06272 ↗First posted 13 Jul 2022cs.LG stat.MLcited by 25

Not on the map. Why?

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.

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

Builds on

54 of 120 references.

References · 54

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  4. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,528
  5. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  6. 2015Pointer Networkscited by 882
  7. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  8. 2019Introduction to Multi-Armed Banditscited by 475
  9. 2017A Tutorial on Thompson Samplingcited by 420
  10. 2017Smart "Predict, then Optimize"cited by 332
  11. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  12. 2017Thinking Fast and Slow with Deep Learning and Tree Searchcited by 245
38 more
  1. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  2. 2018Competitive caching with machine learned advicecited by 194
  3. 2018Learning Scheduling Algorithms for Data Processing Clusterscited by 133
  4. 2014Reinforcement and Imitation Learning via Interactive No-Regret Learningcited by 116
  5. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learningcited by 111
  6. 2019Reinforcement Learning for Integer Programming: Learning to Cutcited by 108
  7. 2019Training Agents using Upside-Down Reinforcement Learningcited by 106
  8. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  9. 2016Causal Bandits: Learning Good Interventions via Causal Inferencecited by 100
  10. 2017Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Predictioncited by 93
  11. 2020Counterfactual Credit Assignment in Model-Free Reinforcement Learningcited by 60
  12. 2020OR-Gym: A Reinforcement Learning Library for Operations Research Problemscited by 50
  13. 2021Heuristic-Guided Reinforcement Learningcited by 41
  14. 2020Queueing Network Controls via Deep Reinforcement Learningcited by 40
  15. 2017Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Methodcited by 30
  16. 2018Variance Reduction for Reinforcement Learning in Input-Driven Environmentscited by 30
  17. 2021Universal Trading for Order Execution with Oracle Policy Distillationcited by 29
  18. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  19. 2018Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learningcited by 24
  20. 2020Robust Asymmetric Learning in POMDPscited by 23
  21. 2019Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory managementcited by 22
  22. 2013PEGASUS: A Policy Search Method for Large MDPs and POMDPscited by 21
  23. 2019Online Allocation and Pricing: Constant Regret via Bellman Inequalitiescited by 16
  24. 2019Adaptive Discretization for Episodic Reinforcement Learning in Metric Spacescited by 16
  25. 2018Learning to Search via Retrospective Imitationcited by 13
  26. 2019The Bayesian Prophet: A Low-Regret Framework for Online Decision Makingcited by 13
  27. 2020PowerNet: Multi-agent Deep Reinforcement Learning for Scalable Powergrid Controlcited by 13
  28. 2020Scalable Deep Reinforcement Learning for Ride-Hailingcited by 12
  29. 2019Learning Compact Models for Planning with Exogenous Processescited by 11
  30. 2017Mean Actor Criticcited by 8
  31. 2021Dynamic Placement in Refugee Resettlementcited by 7
  32. 2021Hindsight Value Function for Variance Reduction in Stochastic Dynamic Environmentcited by 7
  33. 2019Reinforcement learning for bandwidth estimation and congestion control in real-time communicationscited by 6
  34. 2020Outcome-Driven Dynamic Refugee Assignment with Allocation Balancingcited by 6
  35. 2021Policy Gradients Incorporating the Futurecited by 6
  36. 2021Stateful Offline Contextual Policy Evaluation and Learningcited by 6
  37. 2016Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputscited by 5
  38. 2020Lookahead-Bounded Q-Learningcited by 5

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 8; 2024: 7; 2025: 4; 2026: 5.

25 papers.

Sort:

By area:

  1. 2024On Overcoming Miscalibrated Conversational Priors in LLM-based Chatbotscited by 23
  2. 2022Deep Inventory Managementcited by 22
  3. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  4. 2023Sample Efficient Reinforcement Learning in Mixed Systems through Augmented Samples and Its Applications to Queueing Networkscited by 9
  5. 2024VC Theory for Inventory Policiescited by 7
  6. 2023Online Reinforcement Learning in Non-Stationary Context-Driven Environmentscited by 6
  7. 2023Learning an Inventory Control Policy with General Inventory Arrival Dynamicscited by 5
  8. 2023Reinforcement Learning with Exogenous States and Rewardscited by 4
  9. 2023Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observationscited by 4
  10. 2024Neural Coordination and Capacity Control for Inventory Managementcited by 4
  11. 2024Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learningcited by 2
  12. 2025Multi-Agent Reinforcement Learning with Long-Term Performance Objectives for Service Workforce Optimizationcited by 1
13 more
  1. 2025Deep RL Dual Sourcing Inventory Management with Supply and Capacity Risk Awarenesscited by 1
  2. 2026Policy Optimization in Hybrid Discrete-Continuous Action Spaces via Mixed Gradientscited by 1
  3. 2026Minimax PAC Bounds for Learning in Exogenous Contextual MDPscited by 1
  4. 2023Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Informationcited by 0
  5. 2023Optimizing Heat Alert Issuance with Reinforcement Learningcited by 0
  6. 2024Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observationcited by 0
  7. 2024Online design of dynamic networkscited by 0
  8. 2024Zero-shot Generalization in Inventory Management: Train, then Estimate and Decidecited by 0
  9. 2025Scalable Reinforcement Learning for Virtual Machine Schedulingcited by 0
  10. 2025Learning Virtual Machine Scheduling in Cloud Computing through Language Agentscited by 0
  11. 2026Imitation Learning for Combinatorial Optimisation under Uncertaintycited by 0
  12. 2026Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?cited by 0
  13. 2026Ready from Day 1: Population-Aware Coordination for Large-Scale Constrained Multi-Agent Systemscited by 0