Hoai-An Nguyen

Hoai-An Nguyen, Ching-An Cheng

Reinforcement learning (RL) so far has limited real-world applications. One key challenge is that typical RL algorithms heavily rely on a reset mechanism to sample proper initial states; these reset mechanisms, in practice, are expensive to implement due to the need for human intervention or heavily engineered environments. To make learning more practical, we propose a generic no-regret reduction to systematically design reset-free RL algorithms. Our reduction turns the reset-free RL problem into a two-player game. We show that achieving sublinear regret in this two-player game would imply learning a policy that has both sublinear performance regret and sublinear total number of resets in the original RL problem. This means that the agent eventually learns to perform optimally and avoid resets. To demonstrate the effectiveness of this reduction, we design an instantiation for linear Markov decision processes, which is the first provably correct reset-free RL algorithm.

Yang P. Liu, Hoai-An Nguyen, Noah G. Singer et al.

We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dense graphs, we show that $O(n/\varepsilon^2)$ space is sufficient and that $Ω(n)$ space is necessary. In contrast, for graphs with $Θ(n/\varepsilon^2)$ edges, the situation is markedly different: we show that the problem requires $Ω(n \log(\varepsilon^2 n)/\varepsilon^2)$ space for any $\varepsilon=ω(1/\sqrt{n})$, which is tight for the full range of $\varepsilon$. We also give an $Ω(n \log n/\varepsilon^2)$-space lower bound against deterministic algorithms for outputting a $(1-\varepsilon)$ approximation to the value of the maximum cut. Using similar techniques we prove an analogous sharp separation in the streaming space complexity of Densest Subgraph and show that for every constant-arity CSP over a constant-size alphabet and the Similarity problem the space complexity in dense streams can be improved by shaving a logarithmic factor.