Timezone: »

 
Poster
Finding the Stochastic Shortest Path with Low Regret: the Adversarial Cost and Unknown Transition Case
Liyu Chen · Haipeng Luo

Wed Jul 21 09:00 PM -- 11:00 PM (PDT) @ Virtual
in Poster Session 4 »
We make significant progress toward the stochastic shortest path problem with adversarial costs and unknown transition. Specifically, we develop algorithms that achieve $O(\sqrt{S^2ADT_\star K})$ regret for the full-information setting and $O(\sqrt{S^3A^2DT_\star K})$ regret for the bandit feedback setting, where $D$ is the diameter, $T_\star$ is the expected hitting time of the optimal policy, $S$ is the number of states, $A$ is the number of actions, and $K$ is the number of episodes. Our work strictly improves (Rosenberg and Mansour, 2020) in the full information setting, extends (Chen et al., 2020) from known transition to unknown transition, and is also the first to consider the most challenging combination: bandit feedback with adversarial costs and unknown transition. To remedy the gap between our upper bounds and the current best lower bounds constructed via a stochastically oblivious adversary, we also propose algorithms with near-optimal regret for this special case.
Keywords: RL, Decisions and Control Theory
[ Slides] 

Author Information

Liyu Chen (USC)
Haipeng Luo (University of Southern California)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors