Online Learning for Information-Based Sequential Decision-Making and Process Metrics

Read full text Summarise with VIRAT
Authors: Ludovic Schwartz
Cited by: 0
References: 142

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Sequential decision-making is an iterative process between a learner and an environment. At each round, the learner selects an action, receives feedback, and aims to optimize a cumulative performance measure. This framework captures a wide range of applications---including recommender systems, online advertising, adaptive experimentation, and reinforcement learning. A core challenge in all such settings is the \emph{exploration--exploitation} dilemma: the learner must simultaneously gather information about the environment and act in a way that performs well. Two of the most influential design principles for addressing this dilemma are \emph{optimism in the face of uncertainty} (e.g., UCB algorithms) and \emph{Thompson Sampling}. Despite their success, both approaches share an important limitation: they primarily select actions that might be optimal. As a consequence, they do not reliably target actions that are \emph{informative yet suboptimal}, even when such actions would dramatically accelerate learning. This phenomenon can lead to highly suboptimal performance even in simple problems. An alternative approach is \emph{Information Directed Sampling} (IDS), which selects actions by directly optimizing the trade-off between regret and information gain through the information ratio. IDS can overcome the shortcomings of optimism and Thompson Sampling, but existing theory is largely restricted to the Bayesian setting. The first part of this thesis develops and extends this regret--information trade-off paradigm using techniques from online learning, including regret analysis and exponential-weights-based methods. We introduce a lifted information ratio suitable for contextual bandits, construct a frequentist version of IDS via an optimistic surrogate model, and design adaptive algorithms in high-dimensional structured settings. The second part of this thesis concerns a different problem: defining and computing distances between stochastic processes, in particular Markov chains. Defining such distances is challenging, and optimal-transport (OT) based metrics provide a principled and widely studied approach. Although this problem is conceptually distinct from sequential decision-making, three natural connections arise. First, computing OT distances can be reformulated as a sequential decision-making problem, and we leverage this viewpoint to design efficient algorithms. Second, such distances may serve as useful tools for representation learning or state abstraction in reinforcement learning. Third, as in the first part, our methods rely on online learning techniques---most notably regret minimization, mirror descent, and primal--dual optimization. Our contributions are two-fold. We propose a new linear programming formulation of optimal transport between Markov chains based on \emph{discounted occupancy couplings}, which leads to Sinkhorn Value Iteration (SVI)---a scalable algorithm inspired by entropy-regularized optimal transport. We then address the main limitation of existing methods, including SVI: the need for full knowledge of transition dynamics. We design SOMCOT, a stochastic primal--dual algorithm that computes such distances using only sample access to the chains (the first such method with theoretical guarantees).

Fields of Study & Subjects

Advanced Bandit Algorithms Research Reinforcement Learning in Robotics Optimization and Search Problems

Publication details

Journal / source
Tesis Doctorals en Xarxa (Consorci de Serveis Universitaris de Catalunya)
Publication date
20 February 2026
Language
EN
Document type
Thesis