24 citations · 86 across the 22 of their papers we have counts for
4 papers · 1 filter
The complexity of non-stationary reinforcement learning
Christos Papadimitriou, Binghui Peng
The problem of continual learning in the domain of reinforcement learning, often called non-stationary reinforcement learning, has been identified as an important challenge to the…
Memory-Query Tradeoffs for Randomized Convex Optimization
Xi Chen, Binghui Peng
We show that any randomized first-order algorithm which minimizes a -dimensional, -Lipschitz convex function over the unit ball must either use bits of memory or…
Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules
Xi Chen, Binghui Peng
We study the complexity of finding an approximate (pure) Bayesian Nash equilibrium in a first-price auction with common priors when the tie-breaking rule is part of the input. We s…
Near Optimal Memory-Regret Tradeoff for Online Learning
Binghui Peng, Aviad Rubinstein
In the experts problem, on each of days, an agent needs to follow the advice of one of ``experts''. After each day, the loss associated with each expert's advice is reveale…