Optimal decision making under uncertainty

Usual contributors:

Philippe Rolet, Jean-Baptiste Hoock, Arpad Rimmel, Lou Fédon, Romaric Gaudel, Olivier Teytaud, Cyril Furthlener

What we are working on:

• Optimal decision under uncertainty
  • MoGo
  
  A nice game won by mogo in Portland, 2008
  • Energy management
  • Active Learning (Philippe Rolet)
  • Non-linear Optimization (Anne Auger, Olivier Teytaud)
  • Combinatorial Optimization (Cyril Furthlener, Arpad Rimmel)
• Learning on sequential data (Lou Fédon)
  • Hidden Markov Models
  • Recurrent Neural Networks
  • Modifying the database of examples (Romaric Gaudel)

---

Generality of the MoGo approach

MoGo uses Multi-Armed Bandit algorithms and it has to be noticed that no expert Go knowledge was used during MoGo development until very recently when some 9x9 openings were added. In particular, the approach, based on some adaptive Monte-Carlo method, does not require any evaluation function, and is hence not specific to the game of Go.
Of course, the game of Go is the most visible application, easy to experiment with and to demonstrate, but it is merely a toy problem, and we have used very simular approaches to tackle problems that have nothing to do with Go ro games:

• Expensive non-linear optimization: in case of Bayesian prior on the distribution of problems, when computing time is very large, the approach is tractable thanks to a "MoGo-like algorithm (Auger, A. and Teytaud, O.. Continuous Lunches are free plus the design of optimal optimization algorithms. To appear in Algorithmica. 2009).

• Optimal Active Learning: here again, tractability was obtained using some MoGo-like algoritm (Ph. Rollet's PhD, submitted to JMLR).

• A PASCAL Challenge organised by Touch Clarity Ltd was won by TAO using yet another instance of a Multi-Armed Bandit algorithm, (though different from that of MoGo: this dynamic variant of the Multi-Armed Bandit algorithm uses the Page-Hinkley change detection test to eventually restart from scratch in case a change is actually detected.

• a proposal is being submitted with a private company working in energy production. The goal is tu use a MoGo-like technique for the planification of electric production.