Algorithms for Decision Making

A broad introduction to algorithms for decision making under uncertainty, introducing the underlying mathematical problem formulations and the algorithms for solving them.Automated decision-making systems or decision-support systems—used in applications that range from aircraft collision avoidance to breast cancer screening—must be designed to account for various sources of uncertainty while carefully balancing multiple objectives. This textbook provides a broad introduction to algorithms for decision making under uncertainty, covering the underlying mathematical problem formulations and the algorithms for solving them. The book first addresses the problem of reasoning about uncertainty and objectives in simple decisions at a single point in time, and then turns to sequential decision problems in stochastic environments where the outcomes of our actions are uncertain. It goes on to address model uncertainty, when we do not start with a known model and must learn how to act through interaction with the environment; state uncertainty, in which we do not know the current state of the environment due to imperfect perceptual information; and decision contexts involving multiple agents. The book focuses primarily on planning and reinforcement learning, although some of the techniques presented draw on elements of supervised learning and optimization. Algorithms are implemented in the Julia programming language. Figures, examples, and exercises convey the intuition behind the various approaches presented. Preface Acknowledgments Introduction Decision Making Applications Methods History Societal Impact Overview I Probabilistic Reasoning Representation Degrees of Belief and Probability Probability Distributions Joint Distributions Conditional Distributions Bayesian Networks Conditional Independence Summary Exercises Inference Inference in Bayesian Networks Inference in Naive Bayes Models Sum-Product Variable Elimination Belief Propagation Computational Complexity Direct Sampling Likelihood Weighted Sampling Gibbs Sampling Inference in Gaussian Models Summary Exercises Parameter Learning Maximum Likelihood Parameter Learning Bayesian Parameter Learning Nonparametric Learning Learning with Missing Data Summary Exercises Structure Learning Bayesian Network Scoring Directed Graph Search Markov Equivalence Classes Partially Directed Graph Search Summary Exercises Simple Decisions Constraints on Rational Preferences Utility Functions Utility Elicitation Maximum Expected Utility Principle Decision Networks Value of Information Irrationality Summary Exercises II Sequential Problems Exact Solution Methods Markov Decision Processes Policy Evaluation Value Function Policies Policy Iteration Value Iteration Asynchronous Value Iteration Linear Program Formulation Linear Systems with Quadratic Reward Summary Exercises Approximate Value Functions Parametric Representations Nearest Neighbor Kernel Smoothing Linear Interpolation Simplex Interpolation Linear Regression Neural Network Regression Summary Exercises Online Planning Receding Horizon Planning Lookahead with Rollouts Forward Search Branch and Bound Sparse Sampling Monte Carlo Tree Search Heuristic Search Labeled Heuristic Search Open-Loop Planning Summary Exercises Policy Search Approximate Policy Evaluation Local Search Genetic Algorithms Cross Entropy Method Evolution Strategies Isotropic Evolutionary Strategies Summary Exercises Policy Gradient Estimation Finite Difference Regression Gradient Likelihood Ratio Reward-to-Go Baseline Subtraction Summary Exercises Policy Gradient Optimization Gradient Ascent Update Restricted Gradient Update Natural Gradient Update Trust Region Update Clamped Surrogate Objective Summary Exercises Actor-Critic Methods Actor-Critic Generalized Advantage Estimation Deterministic Policy Gradient Actor-Critic with Monte Carlo Tree Search Summary Exercises Policy Validation Performance Metric Evaluation Rare Event Simulation Robustness Analysis Trade Analysis Adversarial Analysis Summary Exercises III Model Uncertainty Exploration and Exploitation Bandit Problems Bayesian Model Estimation Undirected Exploration Strategies Directed Exploration Strategies Optimal Exploration Strategies Exploration with Multiple States Summary Exercises Model-Based Methods Maximum Likelihood Models Update Schemes Exploration Bayesian Methods Bayes-Adaptive Markov Decision Processes Posterior Sampling Summary Exercises Model-Free Methods Incremental Estimation of the Mean Q-Learning Sarsa Eligibility Traces Reward Shaping Action Value Function Approximation Experience Replay Summary Exercises Imitation Learning Behavioral Cloning Data Set Aggregation Stochastic Mixing Iterative Learning Maximum Margin Inverse Reinforcement Learning Maximum Entropy Inverse Reinforcement Learning Generative Adversarial Imitation Learning Summary Exercises IV State Uncertainty Beliefs Belief Initialization Discrete State Filter Kalman Filter Extended Kalman Filter Unscented Kalman Filter Particle Filter Particle Injection Summary Exercises Exact Belief State Planning Belief-State Markov Decision Processes Conditional Plans Alpha Vectors Pruning Value Iteration Linear Policies Summary Exercises Offline Belief State Planning Fully Observable Value Approximation Fast Informed Bound Fast Lower Bounds Point-Based Value Iteration Randomized Point-Based Value Iteration Sawtooth Upper Bound Point Selection Sawtooth Heuristic Search Triangulated Value Functions Summary Exercises Online Belief State Planning Lookahead with Rollouts Forward Search Branch and Bound Sparse Sampling Monte Carlo Tree Search Determinized Sparse Tree Search Gap Heuristic Search Summary Exercises Controller Abstractions Controllers Policy Iteration Nonlinear Programming Gradient Ascent Summary Exercises V Multiagent Systems Multiagent Reasoning Simple Games Response Models Dominant Strategy Equilibrium Nash Equilibrium Correlated Equilibrium Iterated Best Response Hierarchical Softmax Fictitious Play Gradient Ascent Summary Exercises Sequential Problems Markov Games Response Models Nash Equilibrium Fictitious Play Gradient Ascent Nash Q-Learning Summary Exercises State Uncertainty Partially Observable Markov Games Policy Evaluation Nash Equilibrium Dynamic Programming Summary Exercises Collaborative Agents Decentralized Partially Observable Markov Decision Processes Subclasses Dynamic Programming Iterated Best Response Heuristic Search Nonlinear Programming Summary Exercises Appendices Mathematical Concepts Measure Spaces Probability Spaces Metric Spaces Normed Vector Spaces Positive Definiteness Convexity Information Content Entropy Cross Entropy Relative Entropy Gradient Ascent Taylor Expansion Monte Carlo Estimation Importance Sampling Contraction Mappings Graphs Probability Distributions Computational Complexity Asymptotic Notation Time Complexity Classes Space Complexity Classes Decidability Neural Representations Neural Networks Feedforward Networks Parameter Regularization Convolutional Neural Networks Recurrent Networks Autoencoder Networks Adversarial Networks Search Algorithms Search Problems Search Graphs Forward Search Branch and Bound Dynamic Programming Heuristic Search Problems Hex World 2048 Cart-Pole Mountain Car Simple Regulator Aircraft Collision Avoidance Crying Baby Machine Replacement Catch Prisoner's Dilemma Rock-Paper-Scissors Traveler's Dilemma Predator-Prey Hex World Multicaregiver Crying Baby Collaborative Predator-Prey Hex World Julia Types Functions Control Flow Packages Convenience Functions References Index