BusinessComputer ScienceAlgorithmsDecision MakingMarkov Decision ProcessesPartially Observable Markov Decision ProcessesReinforcement LearningReinforcement Learning FoundationsSequential Decision-makingStochastic GamesAgent Reinforcement LearningFinite-horizon Decision MakingLearningMarkov GamesOptimal PoliciesReinforcement Learning In GamesReinforcement Learning ModelsReinforcement Learning Theory
Sequential decision making is a fundamental task for intelligent agents interacting over time, requiring them to answer what action to take next. This thesis demonstrates how to answer that question when the current state, action set, reward objective, and agent type are all finite and well‑defined. The work surveys algorithms for optimal or near‑optimal behavior in Markov decision processes, partially observable Markov decision processes, and Markov games, emphasizing algorithmic descriptions and problem complexity from a computer‑science perspective. New results include an exact finite‑horizon POMDP solver, a minimax‑optimal policy learner for Markov games, a pseudopolynomial bound for policy iteration, and a complete complexity theory for zero‑reward POMDP policies.
Sequential decision making is a fundamental task faced by any intelligent agent in an extended interaction with its environment; it is the act of answering the question ``What should I do now?'''' In this thesis, I show how to answer this question when ``now'''' is one of a finite set of states, ``do'''' is one of a finite set of actions, ``should'''' is maximize a long-run measure of reward, and ``I'''' is an automated planning or learning system (agent). In particular, I collect basic results concerning methods for finding optimal (or near-optimal) behavior in several different kinds of model environments: Markov decision processes, in which the agent always knows its state; partially observable Markov decision processes (POMDPs), in which the agent must piece together its state on the basis of observations it makes; and Markov games, in which the agent is in direct competition with an opponent. The thesis is written from a computer-science perspective, meaning that many mathematical details are not discussed, and descriptions of algorithms and the complexity of problems are emphasized. New results include an improved algorithm for solving POMDPs exactly over finite horizons, a method for learning minimax-optimal policies for Markov games, a pseudopolynomial bound for policy iteration, and a complete complexity theory for finding zero-reward POMDP policies.