A Theory of Bounded Inductive Rationality
Caspar Oesterheld Abram Demski Vincent Conitzer
The dominant theories of rational choice assume logical omniscience. That is,
they assume that when facing a decision problem, an agent can perform all
relevant computations and determine the truth value of all relevant
logical/mathematical claims. This assumption is unrealistic when, for example,
we offer bets on remote digits of pi or when an agent faces a computationally
intractable planning problem. Furthermore, the assumption of logical
omniscience creates contradictions in cases where the environment can contain
descriptions of the agent itself. Importantly, strategic interactions as
studied in game theory are decision problems in which a rational agent is
predicted by its environment (the other players). In this paper, we develop a
theory of rational decision making that does not assume logical omniscience. We
consider agents who repeatedly face decision problems (including ones like
betting on digits of pi or games against other agents). The main contribution
of this paper is to provide a sensible theory of rationality for such agents.
Roughly, we require that a boundedly rational inductive agent tests each
efficiently computable hypothesis infinitely often and follows those hypotheses
that keep their promises of high rewards. We then prove that agents that are
rational in this sense have other desirable properties. For example, they learn
to value random and pseudo-random lotteries at their expected reward. Finally,
we consider strategic interactions between different agents and prove a folk
theorem for what strategies bounded rational inductive agents can converge to.