The Speakers

Title: Recurrent Natural Policy Gradient for POMDPs

Abstract:  We study a natural policy gradient method based on recurrent neural networks (RNNs) for partially-observable Markov decision processes, whereby RNNs are used for policy parameterization and policy evaluation to address curse of dimensionality in non-Markovian reinforcement learning. We present finite-time and finite-width analyses for both the critic (recurrent temporal difference learning), and correspondingly-operated recurrent natural policy gradient method in the near-initialization regime. Our analysis demonstrates the efficiency of RNNs for problems with short-term memory with explicit bounds on the required network widths and sample complexity, and points out the challenges in the case of long-term dependencies.

Joint work with Prof. Semih Cayci (https://www.mathc.rwth-aachen.de/en/~cayci)

Title: Online Learning for Control

Abstract: OLC

Title: Compressive Sensing for Zeroth-Order Gradient Estimation in Online Convex Optimization

Abstract: We tackle the problem of online convex optimization in scenarios where the gradient of the objective function is sparse, meaning that only a few dimensions have non-zero gradients. Our goal is to utilize this sparsity to derive accurate gradient estimates, even with access to only a limited set of function evaluations. This work is motivated by distributed queueing systems, such as those found in microservices-based applications that handle request-response workloads. In such systems, each request type passes through a series of microservices, and resource allocation across these microservices is managed to strike a balance between end-to-end latency and resource usage. Although the number of microservices can be large, the latency function is mainly sensitive to resource changes in just a few of them, leading to sparse gradients. We introduce a method that integrates simultaneous perturbation and compressive sensing to estimate gradients efficiently. We provide theoretical bounds on the number of compressive sensing samples needed per iteration to achieve bounded bias in gradient estimates, ensuring sub-linear regret. By leveraging sparsity, our approach significantly reduces the number of samples required per iteration to match the gradient’s sparsity rather than the full dimensionality of the problem. Through numerical simulations and tests on real-world microservices, we demonstrate its effectiveness, outperforming several stochastic gradient descent methods and converging rapidly to performance levels similar to policies pre-trained with workload information.

Title: Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems

Abstract: We consider the problem of efficiently routing jobs that arrive into a central queue to a system of heterogeneous servers. Unlike homogeneous systems, a threshold policy, that routes jobs to the slow server(s) when the queue length exceeds a certain threshold, is known to be optimal for the one-fast-one-slow two-server system. But an optimal policy for the multi-server system is unknown and non-trivial to find. While Reinforcement Learning (RL) has been recognized to have great potential for learning policies in such cases, our problem has an exponentially large state space size, rendering standard RL inefficient. In this work, we propose ACHQ, an efficient policy gradient based algorithm with a low dimensional soft threshold policy parameterization that leverages the underlying queueing structure. We provide stationary-point convergence guarantees for the general case and despite the low-dimensional parameterization prove that ACHQ converges to an approximate global optimum for the special case of two servers. Simulations demonstrate an improvement in expected response time of up to ~30% over the greedy policy that routes to the fastest available server. This is joint work with Neharika Jali, Guannan Qu and Weina Wang.

Title: Direct Online Preference Learning for Restless Multi-Armed Bandits with Preference Feedback

Abstract: Restless multi-armed bandits (RMAB) has been widely used to model constrained sequential decision-making problems, where the state of each restless arm evolves according to a Markov chain and each state transition generates a scalar reward. However, the success of RMAB crucially relies on the availability and quality of reward signals. Unfortunately, specifying an exact reward function in practice can be challenging and even infeasible. In this work, we introduce Pref-RMAB, a new RMAB model in the presence of preference signals, where the decision maker only observes pairwise preference feedback rather than scalar reward from the activated arms at each decision epoch. Preference feedback, however, arguably contains less information than the scalar reward, which makes Pref-RMAB seemingly more difficult. To address this challenge, we present a direct online preference learning (DOPL) algorithm for Pref-RMAB to efficiently explore the unknown environments, adaptively collect preference data in an online manner, and directly leverage the preference feedback for decision-making. We prove that DOPL yields the first-ever sublinear regret for RMAB with preference feedback. Experimental results further demonstrate the effectiveness of DOPL.

Title: Electric Vehicle Fleet Sizing and Charging Infrastructure Planning

Abstract: We analyze an optimal electric vehicle (EV) fleet and charging infrastructure capacity planning problem in a spatial setting. As customer requests arrive at rate λ, the system operator must determine the minimum number of vehicles and chargers for a given service level along with a matching and charging policy that maximizes the service level. We provide a sharp characterization of the fleet size and the charging infrastructure requirements as the demand grows. We show that an EV system has a fundamentally different scaling due to non-negligible charging times. In addition, we propose the Power-of-d dispatching policy, which achieves near-optimal performance by selecting the d closest vehicles to a trip request and choosing the one with the highest battery level. We conduct simulations on Chicago transportation data verifying our operational insights.