Constructing Optimal Policies for Agents with Constrained Architecture

Dmitri A. Dolgov, and Edmund H. Durfee

Technical Report, Electrical Engineering and Computer Science, University of Michigan, CSE-TR-476-03. 2003.

Abstract
Optimal behavior is a very desirable property of autonomous agents and, as such, has received much attention over the years. However, making optimal decisions and executing optimal actions typically requires a substantial effort on the part of an agent, and in some situations the agent might lack the necessary sensory, computational, or actuating resources to carry out the optimal policy. In such cases, the agent will have to do the best it can, given its architectural constraints. We distinguish between three ways in which an agent's architecture can affect policy optimality. An agent might have limitations that impact its ability to formulate, operationalize (convert to internal representation), or execute an optimal policy. In this paper, we focus on agents facing the latter two types of limitations. We adopt the Markov decision problem framework in our search for optimal policies and show how gradations of increasingly constrained agent architectures create correspondingly more complex optimization problems ranging from polynomial to NP-complete problems. We also present algorithms based on linear and integer programming that work across a range of such constrained optimization problems.


BibTex
@techreport{ dolgov03cmdptech,
   paperID   = "TR-03",
   number    = "CSE-TR-476-03",
   author    = "Dmitri A. Dolgov and Edmund H. Durfee",
   title     = "Constructing Optimal Policies for Agents with Constrained Architecture",
   year      = "2003",
   institution= "Electrical Engineering and Computer Science, University of Michigan"
}