Markov Decision Processes

1: Resistor circuits and Markov decision processes.

We propose a network model that combines the features of resistor circuits and Markov decision processes (MDP). Such a model provides a stochastic dynamic extension to the classical Wardrop equilibrium principle. In particular,

a) we introduce a novel class of network optimization problems, whose solutions characterize the equilibrium behavior of a population of players trying to solve an MDP where the cost of an action increases with its user volumes;
b) we further extend our model to allow players to have variable population size and heterogeneous planning time windows;
c) we also develop dynamic programming based algorithms for the aforementioned equilibrium problem, whose computation efficiency significantly outperforms commercial software Gurobi.

2: RLC circuits based distributed optimization algorithms.

We design efficient distributed optimization algorithms based on RLC circuits dynamics. Such algorithms empirically improve the convergence behavior of existing methods. In particular,

a) our algorithm extends existing distributed mirror descent algorithms by replacing diffusion with damped oscillation;
b) our algorithm directly generalizes to composite objective setting, and empirically achieves faster convergence than existing methods by allowing constant step size.