Description

ML Seminar: Thomas Moerland (Delft University)

Everyone is welcome to attend the ML seminar 'Monte Carlo Tree Search for Asymmetric Trees' given by  Thomas Moerland.

Abstract:

We present an extension of Monte Carlo Tree Search (MCTS) that strongly
increases its efficiency for trees with asymmetry and/or loops.
Asymmetric termination of search trees introduces a type of uncertainty
for which the standard upper confidence bound (UCB) formula does not
account. Our first algorithm (MCTS-T), which assumes a non-stochastic
environment, backs-up tree structure uncertainty and leverages it for
exploration in a modified UCB formula. Results show vastly improved
efficiency in a well-known asymmetric domain in which MCTS performs
arbitrarily bad. Next, we connect the ideas about asymmetric termination
to the presence of loops in the tree, where the same state appears
multiple times in a single trace. An extension to our algorithm
(MCTS-T+), which in addition to non-stochasticity assumes full state
observability, further increases search efficiency for domains with
loops as well. Benchmark testing on a set of OpenAI Gym and Atari 2600
games indicates that our algorithms always perform better than or at
least equivalent to standard MCTS, and could be first-choice tree search
algorithms for non-stochastic, fully-observable environments.

• Web
• Email: Susanne van Dam
• Phone: 020-592 4189
• iCal

ML Seminar: Jaron Sanders (Delft University)

We have the pleasure to announce our CWI Machine Learning seminar with Jaron Sanders with the title: Optimal Clustering Algorithms in Block Markov Chains

This paper considers cluster detection in Block Markov Chains (BMCs). These Markov chains are characterized by a block structure in their transition matrix. More precisely, the n possible states are divided into a finite number of K groups or clusters, such that states in the same cluster exhibit the same transition rates to other states. One observes a trajectory of the Markov chain, and the objective is to recover, from this observation only, the (initially unknown) clusters. In this paper we devise a clustering procedure that accurately, efficiently, and provably detects the clusters. We first derive a fundamental information-theoretical lower bound on the detection error rate satisfied under any clustering algorithm. This bound identifies the parameters of the BMC, and trajectory lengths, for which it is possible to accurately detect the clusters. We next develop two clustering algorithms that can together accurately recover the cluster structure from the shortest possible trajectories, whenever the parameters allow detection. These algorithms thus reach the fundamental detectability limit, and are optimal in that sense.

• Web
• Email: Susanne van Dam
• Phone: 020-592 4189
• iCal