Monte-Carlo Tree Search

Michèle Sebag

TAO: Theme Apprentissage & Optimization

Acknowledgments: Olivier Teytaud, Sylvain Gelly,

Philippe Rolet, Romaric Gaudel

CP 2012
Foreword

Disclaimer 1
I There is no shortage of tree-based approaches in CP...
I MCTS is about approximate inference (propagation or
pruning: exact inference)
Disclaimer 2
I MCTS is related to Machine Learning
I Some words might have different meanings (e.g. consistency)

Motivations
I CP evolves from “Model + Search” to “Model + Run”: ML
needed
I Which ML problem is this ?
Model + Run

Wanted: For any problem instance, automatically

I Select algorithm/heuristics in a portfolio
I Tune hyper-parameters

A general problem, faced by

I Constraint Programming
I Stochastic Optimization
I Machine Learning, too...
1. Case-based learning / Metric learning
CP Hydra
Input
I Observations Representation

Output
I For any new instance, retrieve the nearest case
I (but what is the metric ?)
2. Supervised Learning
SATzilla
Input
I Observations Representation
I Target (best alg.)

Output: Prediction
I Classification
I Regression
From decision to sequential decision

Arbelaez et al. 11

I In each restart, predict the best heuristics

I ... it might solve the problem;
I otherwise the description is refined; iterate
Can we do better: Select the heuristics which will bring us
where we’ll be in good shape to select the best heuristics to solve
the problem...
3. Reinforcement learning

Features
I An agent, temporally situated
I acts on its environment
I in order to maximize its cumulative reward
Learned output
A policy mapping each state onto an action
Formalisation
Notations
I State space S
I Action space A
I Transition model
I deterministic: s 0 = t(s, a)
a 0
I probabilistic: Ps,s 0 = p(s, a, s ) ∈ [0, 1].

I Reward r (s) bounded

I Time horizon H (finite or infinite)

Goal
I Find policy (strategy) π : S 7→ A
I which maximizes cumulative reward from now to timestep H
hX i
π ∗ = argmax IEst+1 ∼p(st ,π(st ),s) r (st )
Reinforcement learning
Context
In an uncertain environment,
Some actions, in some states, bring (delayed) rewards [with some
probability].
find the policy (state → action)
Goal:
maximizing the expected cumulative reward
This talk is about sequential decision making

I Reinforcement learning:
First learn the optimal policy; then apply it

I Monte-Carlo Tree Search:

Any-time algorithm: learn the next move; play it; iterate.
MCTS: computer-Go as explanatory example
Not just a game: same approaches apply to optimal energy
policy
MCTS for computer-Go and MineSweeper

Go: deterministic transitions

MineSweeper: probabilistic transitions
 The game of Go in one slide

Rules
I Each player puts a stone on the goban, black first
I Each stone remains on the goban, except:

group w/o degree freedom is killed a group with two eyes can’t be killed
I The goal is to control the max. territory
Go as a sequential decision problem

Features
I Size of the state space 2.10170
I Size of the action space 200
I No good evaluation function
I Local and global features (symmetries,
freedom, ...)
I A move might make a difference some
dozen plies later
Setting
I State space S
I Action space A
I Known transition model: p(s, a, s 0 )
I Reward on final states: win or lose

Baseline strategies do not apply:

I Cannot grow the full tree
I Cannot safely cut branches
I Cannot be greedy

Monte-Carlo Tree Search

I An any-time algorithm
I Iteratively and asymmetrically growing a search tree
most promising subtrees are more explored and developed
Overview
Motivations
Monte-Carlo Tree Search
Multi-Armed Bandits
Random phase
Evaluation and Propagation
Advanced MCTS
Rapid Action Value Estimate
Improving the rollout policy
Using prior knowledge
Parallelization
Open problems
MCTS and 1-player games
MCTS and CP
Optimization in expectation
Conclusion and perspectives
Overview
Motivations
Monte-Carlo Tree Search
Multi-Armed Bandits
Random phase
Evaluation and Propagation
Advanced MCTS
Rapid Action Value Estimate
Improving the rollout policy
Using prior knowledge
Parallelization
Open problems
MCTS and 1-player games
MCTS and CP
Optimization in expectation
Conclusion and perspectives
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase
I Add a node
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward
Evaluate
I Update information in visited nodes
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward
Evaluate
I Update information in visited nodes
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward
Evaluate
I Update information in visited nodes
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward
Evaluate
I Update information in visited nodes
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward
Evaluate
I Update information in visited nodes
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward
Evaluate
I Update information in visited nodes
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward
Evaluate
I Update information in visited nodes
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward
Evaluate
I Update information in visited nodes
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward
Evaluate
I Update information in visited nodes
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward New Node
Evaluate
I Update information in visited nodes
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward New Node
Evaluate Random
I Update information in visited nodes Phase
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward New Node
Evaluate Random
I Update information in visited nodes Phase
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward New Node
Evaluate Random
I Update information in visited nodes Phase
Propagate Explored Tree
I Returned solution:
I Path visited most often
Monte-Carlo Tree Search
Kocsis Szepesvári, 06
Gradually grow the search tree:
I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward New Node
Evaluate Random
I Update information in visited nodes Phase
Propagate Explored Tree
I Returned solution:
I Path visited most often
MCTS Algorithm

Main
Input: number N of tree-walks
Initialize search tree T ← initial state
Loop: For i = 1 to N
TreeWalk(T , initial state )
EndLoop
Return most visited child node of root node
MCTS Algorithm, ctd
Tree walk
Input: search tree T , state s
Output: reward r

If s is not a leaf node

Select a∗ = argmax {µ̂(s, a), tr (s, a) ∈ T }
r ← TreeWalk(T , tr (s, a∗ ))
Else
As = { admissible actions not yet visited in s}
Select a∗ in As
Add tr (s, a∗ ) as child node of s
r ← RandomWalk(tr (s, a∗ ))
End If

Update ns , ns,a∗ and µ̂s,a∗

Return r
MCTS Algorithm, ctd

Random walk
Input: search tree T , state u
Output: reward r

Arnd ← {} // store the set of actions visited in the random phase

While u is not final state
Uniformly select an admissible action a for u
Arnd ← Arnd ∪ {a}
u ← tr(u, a)
EndWhile

r = Evaluate(u) //reward vector of the tree-walk

Return r
Monte-Carlo Tree Search

Properties of interest
I Consistency: Pr(finding optimal path) → 1 when
the number of tree-walks go to infinity
I Speed of convergence; can be exponentially slow.

Coquelin Munos 07
Comparative results
2012 MoGoTW used for physiological measurements of human players
2012 7 wins out of 12 games against professional players and 9 wins out of 12 games against 6D players
MoGoTW
2011 20 wins out of 20 games in 7x7 with minimal computer komi MoGoTW
2011 First win against a pro (6D), H2, 13×13 MoGoTW
2011 First win against a pro (9P), H2.5, 13×13 MoGoTW
2011 First win against a pro in Blind Go, 9×9 MoGoTW
2010 Gold medal in TAAI, all categories MoGoTW
19×19, 13×13, 9×9
2009 Win against a pro (5P), 9× 9 (black) MoGo
2009 Win against a pro (5P), 9× 9 (black) MoGoTW
2008 in against a pro (5P), 9× 9 (white) MoGo
2007 Win against a pro (5P), 9× 9 (blitz) MoGo
2009 Win against a pro (8P), 19× 19 H9 MoGo
2009 Win against a pro (1P), 19× 19 H6 MoGo
2008 Win against a pro (9P), 19× 19 H7 MoGo
Overview
Motivations
Monte-Carlo Tree Search
Multi-Armed Bandits
Random phase
Evaluation and Propagation
Advanced MCTS
Rapid Action Value Estimate
Improving the rollout policy
Using prior knowledge
Parallelization
Open problems
MCTS and 1-player games
MCTS and CP
Optimization in expectation
Conclusion and perspectives
Action selection as a Multi-Armed Bandit problem

Lai, Robbins 85

In a casino, one wants to maximize

one’s gains while playing.
Lifelong learning

Exploration vs Exploitation Dilemma

I Play the best arm so far ? Exploitation
I But there might exist better arms... Exploration
The multi-armed bandit (MAB) problem

I K arms
I Each arm gives reward 1 with probability µi , 0 otherwise
I Let µ∗ = argmax{µ1 , . . . µK }, with ∆i = µ∗ − µi
I In each time t, one selects an arm it∗ and gets a reward rt
Pt
ni,t = u=1 I1iu∗ =i number of times i has been selected
1 P
µ̂i,t = ni,t iu∗ =i ru average reward of arm i
Pt
Goal: Maximize u=1 ru
⇔
t
X XK K
X
∗ ∗
Minimize Regret (t) = (µ −ru ) = tµ − ni,t µ̂i,t ≈ ni,t ∆i
u=1 i=1 i=1
The simplest approach: -greedy selection

At each time t,
I With probability 1 − ε
select the arm with best empirical reward

it∗ = argmax{µ̂1,t , . . . µ̂K ,t }

I Otherwise, select it∗ uniformly in {1 . . . K }

Regret (t) > εt K1

P
i ∆i

Optimal regret rate: log (t) Lai Robbins 85

Upper Confidence Bound

Auer et al. 2002

( s P )
log ( nj,t )
Select it∗ = argmax µ̂i,t + C
ni,t

Arm A
Arm A
Arm B

Arm A

Arm B Arm B

Decision: Optimism in front of unknown !

Upper Confidence bound, followed
UCB achieves the optimal regret rate log (t)
( s P )
∗ log ( nj,t )
Select it = argmax µ̂i,t + ce
ni,t

Extensions and variants

I Tune ce control the exploration/exploitation trade-off
I UCB-tuned: take into account the standard deviation of µ̂i :
Select it∗ = argmax
 v s !
u
 u log (P nj,t ) 1 2
P
log ( nj,t ) 
µ̂i,t + tce + min , σ̂i,t + ce
 ni,t 4 ni,t 

I Many-armed bandit strategies

I Extension of UCB to trees: UCT Kocsis & Szepesvári, 06
Monte-Carlo Tree Search. Random phase

Gradually grow the search tree:

I Iterate Tree-Walk
I Building Blocks
I Select next action
Bandit phase Bandit−Based
I Add a node Phase
Grow a leaf of the search tree Search Tree
I Select next action bis
Random phase, roll-out
I Compute instant reward New Node
Evaluate Random
I Update information in visited nodes Phase
Propagate Explored Tree
I Returned solution:
I Path visited most often
Random phase − Roll-out policy

Monte-Carlo-based Brügman 93
1. Until the goban is filled,
add a stone (black or white in turn)
at a uniformly selected empty position
2. Compute r = Win(black)
3. The outcome of the tree-walk is r
Random phase − Roll-out policy

Monte-Carlo-based Brügman 93
1. Until the goban is filled,
add a stone (black or white in turn)
at a uniformly selected empty position
2. Compute r = Win(black)
3. The outcome of the tree-walk is r

Improvements ?
I Put stones randomly in the neighborhood of a previous stone
I Put stones matching patterns prior knowledge
I Put stones optimizing a value function Silver et al. 07
Evaluation and Propagation

The tree-walk returns an evaluation r win(black)

Propagate
I For each node (s, a) in the tree-walk

ns,a ← ns,a + 1
1
µ̂s,a ← µ̂s,a + ns,a (r − µs,a )
Evaluation and Propagation

The tree-walk returns an evaluation r win(black)

Propagate
I For each node (s, a) in the tree-walk

ns,a ← ns,a + 1
1
µ̂s,a ← µ̂s,a + ns,a (r − µs,a )

Variants Kocsis & Szepesvári, 06


min{µ̂x , x child of (s, a)} if (s, a) is a black node
µ̂s,a ←
max{µ̂x , x child of (s, a)} if (s, a) is a white node
Dilemma

I smarter roll-out policy →

more computationally expensive →
less tree-walks on a budget

I frugal roll-out →
more tree-walks →
more confident evaluations
Overview
Motivations
Monte-Carlo Tree Search
Multi-Armed Bandits
Random phase
Evaluation and Propagation
Advanced MCTS
Rapid Action Value Estimate
Improving the rollout policy
Using prior knowledge
Parallelization
Open problems
MCTS and 1-player games
MCTS and CP
Optimization in expectation
Conclusion and perspectives
Action selection revisited

( s )
log (ns )
Select a∗ = argmax µ̂s,a + ce
ns,a

I Asymptotically optimal
I But visits the tree infinitely often !

Being greedy is excluded not consistent

Frugal and consistent

Nb win(s, a) + 1
Select a∗ = argmax
Nb loss(s, a) + 2
Berthier et al. 2010
Further directions
I Optimizing the action selection rule Maes et al., 11
Controlling the branching factor
What if many arms ? degenerates into exploration
I Continuous heuristics
Use a small exploration constant ce
I Discrete heuristics Progressive Widening
Coulomp06; Rolet et al. 09
Limit the number of considered actions to b b n(s)c
(usually b = 2 or 4)
considered actions
Number of

Number of iterations

p p
Introduce a new action when b b n(s) + 1c > b b n(s)c
(which one ? See RAVE, below).
RAVE: Rapid Action Value Estimate
Gelly Silver 07
Motivation
I It needs some time to decrease the variance of µ̂s,a
I Generalizing across the tree ?

s
a a a
a
a a
RAVE (s, a) = a
average {µ̂(s 0 , a), s parent of s 0 }
a

local RAVE
global RAVE
Rapid Action Value Estimate, 2

Using RAVE for action selection

In the action selection rule, replace µ̂s,a by

αµ̂s,a + (1 − α) (βRAVE` (s, a) + (1 − β)RAVEg (s, a))

ns,a nparent(s)
α= ns,a +c1 β= nparent(s) +c2

Using RAVE with Progressive Widening

p p
I PW: introduce a new action if b b n(s) + 1c > b b n(s)c

I Select promising actions: it takes time to recover from bad

ones
I Select argmax RAVE` (parent(s)).
A limit of RAVE
I Brings information from bottom to top of tree
I Sometimes harmful:

B2 is the only good move for white

B2 only makes sense as first move (not in subtrees)
⇒ RAVE rejects B2.
Improving the roll-out policy π

π0 Put stones uniformly in empty positions

πrandom Put stones uniformly in the neighborhood of a previous stone
πMoGo Put stones matching patterns prior knowledge
πRLGO Put stones optimizing a value function Silver et al. 07

Beware! Gelly Silver 07

π better π 0 6⇒ MCTS(π) better MCTS(π 0 )

Improving the roll-out policy π, followed
πRLGO against πrandom πRLGO against πMoGo

Evaluation error on 200 test cases

Interpretation

What matters:
I Being biased is more harmful than being weak...
I Introducing a stronger but biased rollout policy π is
detrimental.

if there exist situations where you (wrongly) think you are in good shape
then you go there
and you are in bad shape...
Using prior knowledge

Assume a value function Qprior (s, a)

I Then when action a is first considered in state s, initialize

ns,a = nprior (s, a) equivalent experience / confidence of priors

µs,a = Qprior (s, a)

The best of both worlds

I Speed-up discovery of good moves
I Does not prevent from identifying their weaknesses
Overview
Motivations
Monte-Carlo Tree Search
Multi-Armed Bandits
Random phase
Evaluation and Propagation
Advanced MCTS
Rapid Action Value Estimate
Improving the rollout policy
Using prior knowledge
Parallelization
Open problems
MCTS and 1-player games
MCTS and CP
Optimization in expectation
Conclusion and perspectives
Parallelization. 1 Distributing the roll-outs

comp. comp
node 1 node k

Distributing roll-outs on different computational nodes does not

work.
Parallelization. 2 With shared memory

comp. comp
node 1 node k

I Launch tree-walks in parallel on the same MCTS

I (micro) lock the indicators during each tree-walk update.
Use virtual updates to enforce the diversity of tree walks.
Parallelization. 3. Without shared memory

comp. comp
node 1 node k

I Launch one MCTS per computational node

I k times per second k=3
I Select nodes with sufficient number of simulations
> .05 × # total simulations
I Aggregate indicators

Good news
Parallelization with and without shared memory can be combined.
It works !

32 cores against Winning rate on 9 × 9 Winning rate on 19 × 19

1 75.8 ± 2.5 95.1 ± 1.4
2 66.3 ± 2.8 82.4 ± 2.7
4 62.6± 2.9 73.5 ± 3.4
8 59.6± 2.9 63.1 ± 4.2
16 52± 3. 63 ± 5.6
32 48.9± 3. 48 ± 10

Then:
I Try with a bigger machine ! and win against top professional
players !
I Not so simple... there are diminishing returns.
Increasing the number N of tree-walks

N 2N against N
Winning rate on 9 × 9 Winning rate on 19 × 19
1,000 71.1 ± 0.1 90.5 ± 0.3
4,000 68.7 ± 0.2 84.5 ± 0,3
16,000 66.5± 0.9 80.2 ± 0.4
256,000 61± 0,2 58.5 ± 1.7
The limits of parallelization

R. Coulom

Improvement in terms of performance against humans

Improvement in terms of performance against computers

Improvements in terms of self-play

Overview
Motivations
Monte-Carlo Tree Search
Multi-Armed Bandits
Random phase
Evaluation and Propagation
Advanced MCTS
Rapid Action Value Estimate
Improving the rollout policy
Using prior knowledge
Parallelization
Open problems
MCTS and 1-player games
MCTS and CP
Optimization in expectation
Conclusion and perspectives
Failure: Semeai
Failure: Semeai
Failure: Semeai
Failure: Semeai
Failure: Semeai
Failure: Semeai
Failure: Semeai
Failure: Semeai
Failure: Semeai

Why does it fail

I First simulation gives 50%
I Following simulations give 100% or 0%
I But MCTS tries other moves: doesn’t see all moves on the
black side are equivalent.
Implication 1

MCTS does not detect invariance → too short-sighted

and parallelization does not help.
Implication 2

MCTS does not build abstractions → too short-sighted

and parallelization does not help.
Overview
Motivations
Monte-Carlo Tree Search
Multi-Armed Bandits
Random phase
Evaluation and Propagation
Advanced MCTS
Rapid Action Value Estimate
Improving the rollout policy
Using prior knowledge
Parallelization
Open problems
MCTS and 1-player games
MCTS and CP
Optimization in expectation
Conclusion and perspectives
MCTS for one-player game
I The MineSweeper problem
I Combining CSP and MCTS
Motivation

I All locations have same probability of

death 1/3
I Are then all moves equivalent ?
Motivation

I All locations have same probability of

death 1/3
I Are then all moves equivalent ? NO !
Motivation

I All locations have same probability of

death 1/3
I Are then all moves equivalent ? NO !
I Top, Bottom: Win with probability 2/3
Motivation

I All locations have same probability of

death 1/3
I Are then all moves equivalent ? NO !
I Top, Bottom: Win with probability 2/3
I MYOPIC approaches LOSE.
MineSweeper, State of the art

Markov Decision Process Very expensive; 4 × 4 is solved

Single Point Strategy (SPS) local solver

CSP
I Each unknown location j, a variable x[j]
I Each visible location, a constraint, e.g. loc(15) = 4 →

x[04] + x[05] + x[06] + x[14] + x[16] + x[24] + x[25] + x[26] = 4

I Find all N solutions

number of solutions with mine in j
I P(mine in j) = N
I Play j with minimal P(mine in j)
Constraint Satisfaction for MineSweeper

State of the art

I 80% success beginner (9x9, 10 mines)
I 45% success intermediate (16x16, 40 mines)
I 34% success expert (30x40, 99 mines)

PROS
I Very fast

CONS
I Not optimal
I Beware of first move
(opening book)
Upper Confidence Tree for MineSweeper
Couetoux Teytaud 11
I Cannot compete with CSP in terms of speed
I But consistent (find the optimal solution if given enough time)

Lesson learned
I Initial move matters
I UCT improves on CSP
I 3x3, 7 mines
I Optimal winning rate: 25%
I Optimal winning rate if
uniform initial move: 17/72
I UCT improves on CSP by
1/72
UCT for MineSweeper

Another example
I 5x5, 15 mines
I GnoMine rule (first move gets 0)
I if 1st move is center, optimal winning rate is 100 %
I UCT finds it; CSP does not.
The best of both worlds

CSP
I Fast
I Suboptimal (myopic)

UCT
I Needs a generative model
I Asymptotic optimal

Hybrid
I UCT with generative model based on CSP
UCT needs a generative model
Given
I A state, an action
I Simulate possible transitions
Initial state, play top left
probabilistic transitions

Simulating transitions
I Using rejection (draw mines and check if consistent) SLOW
I Using CSP FAST
The algorithm: Belief State Sampler UCT

I One node created per simulation/tree-walk

I Progressive widening
I Evaluation by Monte-Carlo simulation
I Action selection: UCB tuned (with variance)
I Monte-Carlo moves
I If possible, Single Point Strategy (can propose riskless moves if
any)
I Otherwise, move with null probability of mines (CSP-based)
I Otherwise, with probability .7, move with minimal probability
of mines (CSP-based)
I Otherwise, draw a hidden state compatible with current
observation (CSP-based) and play a safe move.
The results

I BSSUCT: Belief State Sampler UCT

I CSP-PGMS: CSP + initial moves in the corners
Partial conclusion

Given a myopic solver

I It can be combined with MCTS / UCT:
I Significant (costly) improvements
Overview
Motivations
Monte-Carlo Tree Search
Multi-Armed Bandits
Random phase
Evaluation and Propagation
Advanced MCTS
Rapid Action Value Estimate
Improving the rollout policy
Using prior knowledge
Parallelization
Open problems
MCTS and 1-player games
MCTS and CP
Optimization in expectation
Conclusion and perspectives
Active Learning, position of the problem

Supervised learning, the setting

I Target hypothesis h∗
I Training set E = {(xi , yi ), i = 1 . . . n}
I Learn hn from E

Criteria
I Consistency: hn → h∗ when n → ∞.
I Sample complexity: number of examples needed to reach the
target with precision 

 → n s.t. ||hn − h∗ || < 

Active Learning, definition

Passive learning iid examples

E = {(xi , yi ), i = 1 . . . n}

Active learning
xn+1 selected depending on {(xi , yi ), i = 1 . . . n}
In the best case, exponential improvement:
A motivating application

Numerical Engineering

I Large codes
I Computationally heavy ∼
days
I not fool-proof

Inertial Confinement Fusion, ICF

Goal

Simplified models
I Approximate answer
I ... for a fraction of the computational cost
I Speed-up the design cycle
I Optimal design More is Different
Active Learning as a Game

Ph. Rolet, 2010

E: Training data set
Optimization problem A: Machine Learning algorithm
Z: Set of instances
Find F ∗ = argmin
IEh∼A(E,σ,T ) Err(h, σ, T ) σ : E 7→ Z sampling strategy
T : Time horizon
Err: Generalization error
Bottlenecks
I Combinatorial optimization problem
I Generalization error unknown
Where is the game ?
I Wanted: a good strategy to find, as accurately as possible,
the true target concept.
I If this is a game, you play it only once !
I But you can train...

Training game: Iterate

I Draw a possible goal (fake target concept h∗ ); use it as oracle
I Try a policy (sequence of instances
Eh∗ ,T = {(x1 , h∗ (x1 )), . . . (xT , h∗ (xT ))}
I Evaluate: Learn h from Eh∗ ,T . Reward = ||h − h∗ ||
BAAL: Outline
s0

x0 x1 … xP

0 1 h(x1)=0 1 0 1

s00 s01 s10 s11

s00 s01 s10 s11

sT
Overview
Motivations
Monte-Carlo Tree Search
Multi-Armed Bandits
Random phase
Evaluation and Propagation
Advanced MCTS
Rapid Action Value Estimate
Improving the rollout policy
Using prior knowledge
Parallelization
Open problems
MCTS and 1-player games
MCTS and CP
Optimization in expectation
Conclusion and perspectives
Conclusion

Take-home message: MCTS/UCT

I enables any-time smart look-ahead for better sequential
decisions in front of uncertainty.
I is an integrated system involving two main ingredients:
I Exploration vs Exploitation rule UCB, UCBtuned, others
I Roll-out policy
I can take advantage of prior knowledge

Caveat
I The UCB rule was not an essential ingredient of MoGo
I Refining the roll-out policy 6⇒ refining the system
Many tree-walks might be better than smarter (biased) ones.
On-going, future, call to arms

Extensions
I Continuous bandits: action ranges in a IR Bubeck et al. 11
d
I Contextual bandits: state ranges in IR Langford et al. 11
I Multi-objective sequential optimization Wang Sebag 12

Controlling the size of the search space

I Building abstractions
I Considering nested MCTS (partially observable settings, e.g.
poker)
I Multi-scale reasoning
Bibliography
I Peter Auer, Nicolò Cesa-Bianchi, Paul Fischer: Finite-time
Analysis of the Multiarmed Bandit Problem. Machine
Learning 47(2-3): 235-256 (2002)
I Vincent Berthier, Hassen Doghmen, Olivier Teytaud:
Consistency Modifications for Automatically Tuned
Monte-Carlo Tree Search. LION 2010: 111-124
I Sébastien Bubeck, Rémi Munos, Gilles Stoltz, Csaba
Szepesvári: X-Armed Bandits. Journal of Machine Learning
Research 12: 1655-1695 (2011)
I Pierre-Arnaud Coquelin, Rémi Munos: Bandit Algorithms for
Tree Search. UAI 2007: 67-74
I Rémi Coulom: Efficient Selectivity and Backup Operators in
Monte-Carlo Tree Search. Computers and Games 2006: 72-83
I Romaric Gaudel, Michèle Sebag: Feature Selection as a
One-Player Game. ICML 2010: 359-366
I Sylvain Gelly, David Silver: Combining online and offline
knowledge in UCT. ICML 2007: 273-280
I Levente Kocsis, Csaba Szepesvári: Bandit Based Monte-Carlo
Planning. ECML 2006: 282-293
I Francis Maes, Louis Wehenkel, Damien Ernst: Automatic
Discovery of Ranking Formulas for Playing with Multi-armed
Bandits. EWRL 2011: 5-17
I Arpad Rimmel, Fabien Teytaud, Olivier Teytaud: Biasing
Monte-Carlo Simulations through RAVE Values. Computers
and Games 2010: 59-68
I David Silver, Richard S. Sutton, Martin Müller:
Reinforcement Learning of Local Shape in the Game of Go.
IJCAI 2007: 1053-1058
I Olivier Teytaud, Michèle Sebag: Combining Myopic
Optimization and Tree Search: Application to MineSweeper,
LION 2012.