Brendan's Research
main page



Much of this work was done while I was a PhD student in Computer Science at Carnegie Mellon University, advised by Geoff Gordon and Avrim Blum. Now you can find me at Google's Pittsburgh office.

Refereed Publications

  • Sleeping Experts and Bandits with Stochastic Action Availability and Adversarial Rewards
    Varun Kanade, H. Brendan McMahan, and Brent Bryan. To appear in the Proceedings of the 12th International Conference on Artificial Intelligence and Statistic (AISTATS 2009).

  • Robust Submodular Observation Selection
    Andreas Krause, H. Brendan McMahan, Carlos Guestrin, and Anupam Gupta. Journal of Machine Learning Research (JMLR), Volumne 9. [pdf]

  • Selecting Observations Against Adversarial Objectives
    Andreas Krause, H. Brendan McMahan, Carlos Guestrin, and Anupam Gupta. Advances in Neural Information Processing Systems (NIPS 2007). [pdf (with proofs)]

  • A Unification of Extensive-Form Games and Markov Decision Processes
    H. Brendan McMahan and Geoffrey J. Gordon. Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI 2007). [pdf]

  • Efficiently Computing Minimax Expected-Size Confidence Regions
    Brent Bryan, H. Brendan McMahan, Chad M. Schafer, and Jeff Schneider. Proceedings of the 24th Annual International Conference on Machine Learning (ICML 2007). [pdf]

  • A Fast Bundle-based Anytime Algorithm for Poker and other Convex Games
    H. Brendan McMahan and Geoffrey J. Gordon. Proceedings of the 11th International Conference on Artificial Intelligence and Statistics (AISTATS 2007). [pdf]

  • Bounded Real-Time Dynamic Programming: RTDP with monotone upper bounds and performance guarantees
    H. Brendan McMahan, Maxim Likhachev, Geoffrey J Gordon. In Proceedings of the 22nd International Conference on Machine Learning (ICML 2005). [pdf]

  • Fast Exact Planning in Markov Decision Processes
    H. Brendan McMahan and Geoffrey J. Gordon. International Conference on Automated Planning & Scheduling (ICAPS) 2005. (See the TR below for an extended treatment of this topic.) [pdf]

  • Online Convex Optimization in the Bandit Setting: Gradient Descent without a Gradient
    Abraham Flaxman, Adam Kalai, and H. Brendan McMahan. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005). [ps] [pdf]

  • Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary
    H. Brendan McMahan and Avrim Blum. Proceedings of the Seventeenth Annual Conference on Learning Theory (COLT 2004). [ps] [pdf]

  • Planning in the Presence of Cost Functions Controlled by an Adversary
    H. Brendan McMahan, Geoff Gordon, and Avrim Blum. In Proceedings of the 20th International Conference on Machine Learning (ICML 2003). [ps] [pdf] [slides, in pdf]

  • Multi-source Spanning Trees:
    Algorithms for Minimizing Source Eccentricities

    H. Brendan McMahan and Andrzej Proskurowski. In Discrete Applied Mathematics, volume 137/2, 2003 (Special issue: International Workshop on Algorithms, Combinatorics, and Optimization in Interconnection Networks) [ps]

Other Publications

  • Thesis: Robust Planning in Domains with Stochastic Outcomes, Adversaries, and Partial Observability
    H. Brendan McMahan. PhD Thesis, CMU CSD TR, number CMU-CS-06-166. [abstract] [pdf] [ps]

  • Generalizing Dijkstra's Algorithm and Gaussian Elimination
    for Solving MDPs

    H. Brendan McMahan and Geoffrey J Gordon. CMU CSD TR, number CMU-CS-05-127. This is a newer, extended version of the conference paper Fast Exact Planning in Markov Decision Processes. [abstract] [pdf] [ps]

  • Thesis Proposal: Black Box and Generalized Algorithms for Planning in Uncertain Domains
    [abstract] [ps]

  • Planning in Cost-Paired Markov Decision Process Games
    H. Brendan McMahan and Geoff Gordon. NIPS 2003 Workshop on Planning for the Real-World. Extended Abstract [pdf]

Other Research, Projects, and Papers

Solving Large, Sparse Unsymmetric Linear Systems

A talk for the SELECT lab meeting on 9/23/04, describing some linear systems that arise in the solution of MDPs, and a high-level overview of techniques for solving linear systems that might be useful to people in the planning community. I am far from an expert on this, but am trying to learn more. My slides will be available soon. I've put together a limited bibliography that contains a few good starting points for further reading.

A New Form of Partial Redundancy Elimination

This was my class project for CS 745: Optimizing Compilers, together with Tom Murphy. We developed a new form of Partial Redundancy Elimination for programs in Static Single Assignment form that detects redundancies across copy operations. Details and our final report.

Graph Algorithms Research (k-MEST)

During the summer of 1999 I worked at the University of Oregon with Dr. Andrzej Proskurowski on several graph theoretic questions relating to multicast network communication. The results of my main area of investigation are being published as a UO #99-08 Technical Report and are to appear in Discrete Applied Mathematics as "Multi-source spanning trees: algorithms for minimizing source eccentricities." [ps]

Quadratic Forms Defined Over Finite Fields

I spent 9 weeks of the summer of 1998 working with another student on several problems relating to quadratic forms defined over finite fields. Our primary result was a closed form solution for the number of zeros of a quadratic form defined over a finite field of characteristic not two. We implemented several number theoretic algorithms in Java to check conjectures and to provide concrete examples of the main theorem proved. Results were presented to the mathematics faculty at the UK and as a primary talk at the Murdock Charitable Trust Summer Research Conference, 1998. final writeup [ps].

I started to collect some useful links and tools, but this hasn't been getting updated.

Page created and maintained by Brendan McMahan
Last modified: Mon Jan 12 17:35:19 EST 2009