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 19 Acknowledgments 21 Introduction 23 Decision Making 23 Applications 24 Methods 27 History 29 Societal Impact 34 Overview 36 I Probabilistic Reasoning 39 Representation 41 Degrees of Belief and Probability 41 Probability Distributions 42 Joint Distributions 46 Conditional Distributions 51 Bayesian Networks 54 Conditional Independence 57 Summary 58 Exercises 60 Inference 65 Inference in Bayesian Networks 65 Inference in Naive Bayes Models 70 Sum-Product Variable Elimination 71 Belief Propagation 75 Computational Complexity 75 Direct Sampling 76 Likelihood Weighted Sampling 79 Gibbs Sampling 82 Inference in Gaussian Models 85 Summary 87 Exercises 88 Parameter Learning 93 Maximum Likelihood Parameter Learning 93 Bayesian Parameter Learning 97 Nonparametric Learning 104 Learning with Missing Data 104 Summary 111 Exercises 111 Structure Learning 119 Bayesian Network Scoring 119 Directed Graph Search 121 Markov Equivalence Classes 125 Partially Directed Graph Search 126 Summary 128 Exercises 129 Simple Decisions 133 Constraints on Rational Preferences 133 Utility Functions 134 Utility Elicitation 136 Maximum Expected Utility Principle 138 Decision Networks 138 Value of Information 141 Irrationality 144 Summary 147 Exercises 147 II Sequential Problems 153 Exact Solution Methods 155 Markov Decision Processes 155 Policy Evaluation 158 Value Function Policies 161 Policy Iteration 162 Value Iteration 163 Asynchronous Value Iteration 167 Linear Program Formulation 169 Linear Systems with Quadratic Reward 169 Summary 172 Exercises 173 Approximate Value Functions 183 Parametric Representations 183 Nearest Neighbor 185 Kernel Smoothing 186 Linear Interpolation 189 Simplex Interpolation 190 Linear Regression 194 Neural Network Regression 196 Summary 197 Exercises 199 Online Planning 203 Receding Horizon Planning 203 Lookahead with Rollouts 205 Forward Search 205 Branch and Bound 207 Sparse Sampling 209 Monte Carlo Tree Search 209 Heuristic Search 219 Labeled Heuristic Search 219 Open-Loop Planning 222 Summary 230 Exercises 231 Policy Search 235 Approximate Policy Evaluation 235 Local Search 237 Genetic Algorithms 237 Cross Entropy Method 240 Evolution Strategies 241 Isotropic Evolutionary Strategies 246 Summary 248 Exercises 248 Policy Gradient Estimation 253 Finite Difference 253 Regression Gradient 256 Likelihood Ratio 256 Reward-to-Go 259 Baseline Subtraction 263 Summary 267 Exercises 268 Policy Gradient Optimization 271 Gradient Ascent Update 271 Restricted Gradient Update 273 Natural Gradient Update 275 Trust Region Update 276 Clamped Surrogate Objective 279 Summary 285 Exercises 286 Actor-Critic Methods 289 Actor-Critic 289 Generalized Advantage Estimation 291 Deterministic Policy Gradient 294 Actor-Critic with Monte Carlo Tree Search 296 Summary 299 Exercises 299 Policy Validation 303 Performance Metric Evaluation 303 Rare Event Simulation 307 Robustness Analysis 310 Trade Analysis 311 Adversarial Analysis 313 Summary 317 Exercises 317 III Model Uncertainty 319 Exploration and Exploitation 321 Bandit Problems 321 Bayesian Model Estimation 323 Undirected Exploration Strategies 323 Directed Exploration Strategies 325 Optimal Exploration Strategies 328 Exploration with Multiple States 331 Summary 331 Exercises 333 Model-Based Methods 339 Maximum Likelihood Models 339 Update Schemes 340 Exploration 343 Bayesian Methods 348 Bayes-Adaptive Markov Decision Processes 351 Posterior Sampling 352 Summary 354 Exercises 354 Model-Free Methods 357 Incremental Estimation of the Mean 357 Q-Learning 358 Sarsa 360 Eligibility Traces 363 Reward Shaping 365 Action Value Function Approximation 365 Experience Replay 367 Summary 370 Exercises 373 Imitation Learning 377 Behavioral Cloning 377 Data Set Aggregation 380 Stochastic Mixing Iterative Learning 380 Maximum Margin Inverse Reinforcement Learning 383 Maximum Entropy Inverse Reinforcement Learning 387 Generative Adversarial Imitation Learning 391 Summary 393 Exercises 394 IV State Uncertainty 399 Beliefs 401 Belief Initialization 401 Discrete State Filter 402 Kalman Filter 405 Extended Kalman Filter 407 Unscented Kalman Filter 409 Particle Filter 412 Particle Injection 416 Summary 417 Exercises 419 Exact Belief State Planning 429 Belief-State Markov Decision Processes 429 Conditional Plans 430 Alpha Vectors 433 Pruning 434 Value Iteration 438 Linear Policies 441 Summary 441 Exercises 444 Offline Belief State Planning 449 Fully Observable Value Approximation 449 Fast Informed Bound 451 Fast Lower Bounds 452 Point-Based Value Iteration 453 Randomized Point-Based Value Iteration 455 Sawtooth Upper Bound 458 Point Selection 462 Sawtooth Heuristic Search 464 Triangulated Value Functions 467 Summary 469 Exercises 470 Online Belief State Planning 475 Lookahead with Rollouts 475 Forward Search 475 Branch and Bound 478 Sparse Sampling 478 Monte Carlo Tree Search 479 Determinized Sparse Tree Search 481 Gap Heuristic Search 482 Summary 486 Exercises 489 Controller Abstractions 493 Controllers 493 Policy Iteration 497 Nonlinear Programming 500 Gradient Ascent 503 Summary 508 Exercises 508 V Multiagent Systems 513 Multiagent Reasoning 515 Simple Games 515 Response Models 516 Dominant Strategy Equilibrium 519 Nash Equilibrium 520 Correlated Equilibrium 520 Iterated Best Response 525 Hierarchical Softmax 526 Fictitious Play 527 Gradient Ascent 531 Summary 531 Exercises 533 Sequential Problems 539 Markov Games 539 Response Models 541 Nash Equilibrium 542 Fictitious Play 543 Gradient Ascent 548 Nash Q-Learning 548 Summary 550 Exercises 552 State Uncertainty 555 Partially Observable Markov Games 555 Policy Evaluation 557 Nash Equilibrium 559 Dynamic Programming 562 Summary 564 Exercises 564 Collaborative Agents 567 Decentralized Partially Observable Markov Decision Processes 567 Subclasses 568 Dynamic Programming 571 Iterated Best Response 572 Heuristic Search 572 Nonlinear Programming 573 Summary 576 Exercises 578 Appendices 581 Mathematical Concepts 583 Measure Spaces 583 Probability Spaces 584 Metric Spaces 584 Normed Vector Spaces 584 Positive Definiteness 586 Convexity 586 Information Content 587 Entropy 588 Cross Entropy 588 Relative Entropy 589 Gradient Ascent 589 Taylor Expansion 590 Monte Carlo Estimation 591 Importance Sampling 592 Contraction Mappings 592 Graphs 594 Probability Distributions 595 Computational Complexity 597 Asymptotic Notation 597 Time Complexity Classes 599 Space Complexity Classes 599 Decidability 601 Neural Representations 603 Neural Networks 603 Feedforward Networks 604 Parameter Regularization 607 Convolutional Neural Networks 609 Recurrent Networks 610 Autoencoder Networks 614 Adversarial Networks 616 Search Algorithms 621 Search Problems 621 Search Graphs 622 Forward Search 622 Branch and Bound 623 Dynamic Programming 626 Heuristic Search 626 Problems 631 Hex World 631 2048 632 Cart-Pole 633 Mountain Car 634 Simple Regulator 635 Aircraft Collision Avoidance 636 Crying Baby 637 Machine Replacement 639 Catch 641 Prisoner's Dilemma 643 Rock-Paper-Scissors 643 Traveler's Dilemma 644 Predator-Prey Hex World 645 Multicaregiver Crying Baby 646 Collaborative Predator-Prey Hex World 647 Julia 649 Types 649 Functions 662 Control Flow 665 Packages 667 Convenience Functions 670 References 673 Index 693