Date: August 27, 2025
Time: 3:45-5 p.m.
Location: Computing and Information Science Building, Room 450 or via Zoom
Speaker: Dimitrios Christou
Abstract: We consider a class of optimization problems over stochastic variables where the algorithm can learn information about the value of any variable through a series of costly steps; we model this information acquisition process as a Markov Decision Process (MDP). The algorithm's goal is to maximize the value of its solution minus the cost of information acquisition under a selection constraint. Such bandit superprocesses have been studied previously but solutions are known only for fairly restrictive special cases and the problem is computationally challenging in general.
To address this challenge, previous approaches have turned to approximation algorithms by considering a restricted class of committing policies that simplify the decision-making aspects of the problem and allow for efficient optimization. This motivates the question of bounding the commitment gap, measuring the worst case ratio in the performance of the optimal committing policy and the overall optimal.
In this talk, we provide a unified framework for bounding the commitment gap by developing a bound on the utility of the overall optimal through a novel cost amortization technique. We then proceed to develop two different approaches for exploiting that bound. The first one is a local approximation condition that is established individually for each MDP and then composes into a (global) bound on the commitment gap. The second one relies on an ex ante relaxation of the objective and provides MDP-invariant bounds on the commitment gap that are related to the correlation gap of the underlying selection constraint. Both techniques provide improved bounds on the commitment gap and approximately optimal solutions to many costly information models, including different variants of the Pandora’s Box problem.
Bio: Dimitrios (Dimitris) Christou is a 5th year Computer Science Ph.D. student at UT Austin. He is fortunate to be advised by Prof. Shuchi Chawla. Prior to joining UT Austin, he received a Diploma in Electrical and Computer Engineering from the National Technical University of Athens. His research focuses on optimisation in uncertain environments and spans many areas, including the design of online algorithms, online-learning algorithms and data-driven algorithmic design. Recently, he has worked in problems in the intersection of Computer Science, Operations Research and Economics such as revenue maximization in online markets and costly-information models like bandit super-processes.