English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider regret minimization for Adversarial Markov Decision Processes(AMDPs), where the loss functions are changing over time and adversariallychosen, and the learner only observes the losses for the visited state-actionpairs (i.e., bandit feedback). While there has been a surge of studies on thisproblem using Online-Mirror-Descent (OMD) methods, very little is known aboutthe Follow-the-Perturbed-Leader (FTPL) methods, which are usuallycomputationally more efficient and also easier to implement since it onlyrequires solving an offline planning problem. Motivated by this, we take acloser look at FTPL for learning AMDPs, starting from the standard episodicfinite-horizon setting. We find some unique and intriguing difficulties in theanalysis and propose a workaround to eventually show that FTPL is also able toachieve near-optimal regret bounds in this case. More importantly, we then findtwo significant applications: First, the analysis of FTPL turns out to bereadily generalizable to delayed bandit feedback with order-optimal regret,while OMD methods exhibit extra difficulties (Jin et al., 2022). Second, usingFTPL, we also develop the first no-regret algorithm for learning communicatingAMDPs in the infinite-horizon setting with bandit feedback and stochastictransitions. Our algorithm is efficient assuming access to an offline planningoracle, while even for the easier full-information setting, the only existingalgorithm (Chandrasekaran and Tewari, 2021) is computationally inefficient.

Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback