Game theory is the mathematical study of rational behavior in strategic environments. In many settings, most notably two-person zero-sum games, game theory provides particularly strong and appealing solution concepts. Furthermore, these solutions are efficiently computable in the complexity-theory sense. However, in most interesting potential applications in artificial intelligence, the solutions are difficult to compute using current techniques due primarily to the extremely large state-spaces of the environments.

In this thesis, we propose new algorithms for tackling these
computational difficulties. In one stream of research, we introduce
*automated abstraction algorithms for sequential games of
imperfect information*. These algorithms take as input a
description of a game and produce a description of a strategically
similar, but smaller, game as output. We present algorithms that are
lossless (*i.e.,* equilibrium-preserving), as well as algorithms
that are lossy, but which can yield much smaller games while still
retaining the most important features of the original game.

In a second stream of research, we develop *specialized
optimization algorithms for finding ε-equilibria in sequential
games of imperfect information*. The algorithms are based on
recent advances in non-smooth convex optimization (namely the
excessive gap technique) and provide significant improvements over
previous algorithms for finding ε-equilibria.

Combining these two streams, we enable the application of game theory to games extremely larger than was previously possible. As in illustrative example, we find near-optimal solutions for a four-round model of Texas Hold'em poker, and demonstrate that the resulting player is significantly better than previous computer poker players.

In addition to the above (already completed) work, we discuss how
the same techniques can be used to construct an agent for no-limit
Texas Hold'em poker (a game with an infinite number of pure
strategies). We propose coming up with worst-case guarantees (both
*ex ante* and *ex post*) for automated abstraction
algorithms. We also propose a regret-minimizing pure strategy
solution concept appropriate for sequential games with many players,
and propose an algorithm for computing this concept. Finally, we
propose specialized interior-point algorithms for equilibrium
computation in extensive form games (possibly for computing
equilibrium refinements such as sequential equilibrium) as well as a
prioritized updating scheme for speeding up the excessive gap
technique family of algorithms.