The programme below is tentative and may still be subject to minor changes.
| 09:30–09:45 | Opening remarks |
| 09:45–11:15 | Pierre Tarrès — Minicourse (Lecture 1): Self-interacting random walks with and without exchangeability |
| 11:15–11:45 | Coffee break |
| 11:45–12:45 | Steffen Dereich — Title TBA |
| 12:45–14:00 | Lunch break |
| 14:00–15:00 | Johannes Bäumler — Estimating the history of a random recursive tree |
| 15:00–15:30 | Coffee break |
| 15:30–16:30 | Peter Mörters — Branching with selection and mutation |
| 16:30–17:30 | Markus Heydenreich — Preferential Attachment Trees with Vertex Death |
| 09:30–11:00 | Pierre Tarrès — Minicourse (Lecture 2): Self-interacting random walks with and without exchangeability |
| 11:00–11:30 | Coffee break |
| 11:30–12:30 | Silke Rolles — Restrictions of some reinforced processes to subgraphs |
| 12:30–14:00 | Lunch break |
| 14:00–15:00 | Codina Cotar — Title TBA |
| 15:00–15:30 | Coffee break |
| 15:30–16:30 | Nadia Sidorova — Edge-reinforced branching random walk on the triangle |
| 09:30–10:30 | Clemens Heitzinger — Probably Approximately Correct Results for Reinforcement Learning |
| 10:30–11:00 | Coffee break |
| 11:00–12:30 | Pierre Tarrès — Minicourse (Lecture 3): Self-interacting random walks with and without exchangeability |
| 12:30–13:35 | Lunch break |
| 13:35–14:35 | Aurélien Garivier — Distributional Reinforcement Learning via Moment Matching |
| 14:35–15:05 | Coffee break |
| 15:05–16:05 | Leif Döring — On the convergence theory of PPO and Q-learning |
| 16:05–16:15 | Short break |
| 16:15–17:45 | Discussion session: “Probability meets AI” |
| 09:30–10:30 | Stefan Großkinsky — Emergence of Monopoly in Non-linear Pólya Urns |
| 10:30–11:00 | Coffee break |
| 11:00–12:00 | Debleena Thacker — Tampered Memory Elephant Random Walk on the One-dimensional Integer Lattice |
| 12:00–12:15 | Closing remarks |
| 12:15–13:30 | Lunch |
Self-interacting random walks with and without exchangeability
The minicourse will discuss techniques for edge-reinforced random walks and their non-symmetric generalizations, such as partial exchangeability, isomorphism theorems and supersymmetry, random Schrödinger representation, and the link with Bayesian statistics. It will also emphasize recent developments on reinforced random walks that do not satisfy the partial exchangeability property, as well as relevant techniques for proving recurrence/transience, range at a given time, and local time formulas in those cases, with a particular emphasis on the once-reinforced random walk (ORRW).
Estimating the history of a random recursive tree
A random recursive tree (RRT) is a tree that grows one vertex at a time: at each time step, a new node connects to an existing node chosen uniformly at random. Given an unlabelled RRT on \(n\) vertices, we estimate the arrival times of its nodes. Using rankings of influential nodes (centrality), we derive tail bounds for the relative estimation error that are uniform in the vertex and the tree size. For the ranking induced by Jordan centrality, the probability that the estimate exceeds the true arrival time by a factor \(S\) decays on the order of \(1/S\), while the probability that it is smaller than the true arrival time by a factor \(1/S\) decays exponentially in \(S\). We introduce a refined centrality measure whose overestimation probability decays on the order of \((\log S)/S^{2}\), at the cost of a heavier lower tail of order \(1/S^{2}\). These results identify a tradeoff between upper- and lower-tail performance in arrival-time estimation. This is joint work with Simon Briend and Joost Jorritsma.
On the convergence theory of PPO and Q-learning
Abstract to be announced.
Distributional Reinforcement Learning via Moment Matching
In reinforcement learning, an agent typically chooses at each time among a set of Markov kernels so as to maximize some utility function of her path. Distributional Reinforcement Learning (DistRL) aims at estimating the law of the obtained utility. We will present here a DistRL approach that leverage the exact computability of specific moments of the return distribution via generalized dynamic programming. This approach offers a principled and theoretically grounded alternative to existing DistRL policy evaluation and planning methods, with the key advantage to avoid the accumulation of approximations during the iterations. We study the accuracy of generic reconstruction methods of the full return distribution from its computed moments: we prove an error bound on the Wasserstein W1 distance that is independent of the horizon (or discount factor). Then, we focus on the use of the Maximum Entropy principle: under additional regularity assumptions, we prove a much stronger control of the error under the Kullback-Leibler divergence.
Emergence of Monopoly in Non-linear Pólya Urns
Generalized Pólya urns with non-linear feedback are an established probabilistic model to describe the dynamics of competing agents in growth processes with reinforcement. We provide a comprehensive account of the possible asymptotic behaviour for a large general class of feedback, and describe in detail how monopolies emerge in a transition from sub-linear to super-linear feedback via hierarchical states close to linearity. Based on Rubin's exponential embedding, the tail asymptotics for losing agents is related to explosive birth processes conditioned on non-explosion. We also provide a scaling limit for the full time evolution of market shares for diverging initial market size, and apply this to model the dynamics of the wealth distribution through wages and capital returns. This is joint work with Thomas Gottfried (Augsburg).
Probably Approximately Correct Results for Reinforcement Learning
I will present convergence results for probably approximately correct (PAC) learning in the context of reinforcement-learning algorithms. The optimal choice of hyperparameters to speed up convergence resulting from these calculations will also be discussed.
Preferential Attachment Trees with Vertex Death
Preferential attachment models are a popular class of random graphs that have received a wealth of attention in the last decades and are often used to model evolving networks. In such models, new vertices are added to the graph sequentially and new vertices are more likely to make connections with existing vertices that have a large degree. In recent work, we study a general preferential attachment model where vertices can both be added but can also be ‘killed’. Such killed vertices can no longer make new connections, whereas ‘alive’ vertices continue to make new connections. This models evolving networks that can both increase as well as decrease in size. We focus on ‘persistence of the maximum degree’: are the oldest alive vertices also the ones with largest degree? We uncover a novel regime in which killing of vertices makes such persistence entirely impossible. This is based on joint work with Bas Lodewijks.
Branching with selection and mutation
We investigate a stochastic model of a growing population subject to selection and mutation. In our model each individual carries a fitness which determines its mean offspring number. Many of these offspring inherit their parent’s fitness, but some are mutants and obtain a fitness randomly sampled from a fixed distribution. We find the precise rate of growth of the population, identify a regime where a condensation effect occurs and formulate a conjecture for the age and fitness distribution in the population.
Restrictions of some reinforced processes to subgraphs
Processes with reinforcement have been extensively studied in the past decades. Linearly edge-reinforced random walk and the vertex-reinforced jump process are very special because they are mixtures of Markov chains and Markov jump processes, respectively. The restriction of the vertex-reinforced jump process to a subgraph turns out to be a mixture of vertex-reinforced jump processes on the subgraph. This property is used to prove a recurrence result for both the vertex-reinforced jump process and the edge-reinforced random walk on graphs of bounded degree where each edge is replaced by a series of sufficiently many edges. The talk is based on joint work with Margherita Disertori and Franz Merkl.
Edge-reinforced branching random walk on the triangle
Edge-reinforced random walk (ERRW) is a random process on the vertices of a graph that is more likely to cross the edges it has visited in the past. Depending on the strength of the reinforcement, one-dimensional ERRW can either exhibit localisation (eventually moving back and forth across a single edge) or remain transient. We consider a model where a single ERRW is replaced by an exponentially growing number of random particles, and we study its localisation properties on the simple triangle graph. Using the dynamical systems approach we analyse the frequencies with which the edges are traversed and prove their almost sure convergence. We discuss the scenarios when those frequencies become negligible for one or two edges (dominance). We also discuss the situation when an edge stops being traversed entirely (monopoly). This is a joint work with Giordano Giambartolomei.
Tampered Memory Elephant Random Walk on the One-dimensional Integer Lattice
An Elephant Random Walk (ERW) is a discrete-time stochastic process where the next increment is determined by randomly selecting one of the previous steps from the entire history and either repeating it with probability \(p\) or flipping it with probability \(1-p\). This process demonstrates a phase transition into diffusive, critical, and superdiffusive regimes, with criticality at \(p=3/4\). One of the outstanding questions is whether one needs to sample from the entire history to observe this phase transition. To understand the role of memory, we introduce the Tampered Memory Elephant Random Walk (TMERW), where history is partitioned into two disjoint sets \(D_n\) and its complement. On \(D_n^c\), the dynamics are the same as an ERW, while on \(D_n\), the increments are replaced by independent innovations, thus having two competing driving components. We observe that if \(\lim_{n \to \infty} \frac{\lvert D_n^c\rvert}{n} > \frac{1}{2},\) then a phase transition into diffusive, critical, and superdiffusive regimes is still observable, whereas if the limit is less than \(\frac{1}{2}\), there is only the diffusive regime. Thus, one-half emerges as the sharp breakpoint, and the superdiffusive regime (anomalous diffusion) persists only when we tamper with less than half of the memory. This is joint work with Vinita Mulay and Neeraja Sahasrabudhe.