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 derive a novel asymptotic problem-dependent lower-bound for regretminimization in finite-horizon tabular Markov Decision Processes (MDPs). While,similar to prior work (e.g., for ergodic MDPs), the lower-bound is the solutionto an optimization problem, our derivation reveals the need for an additionalconstraint on the visitation distribution over state-action pairs thatexplicitly accounts for the dynamics of the MDP. We provide a characterizationof our lower-bound through a series of examples illustrating how different MDPsmay have significantly different complexity. 1) We first consider a "difficult"MDP instance, where the novel constraint based on the dynamics leads to alarger lower-bound (i.e., a larger regret) compared to the classical analysis.2) We then show that our lower-bound recovers results previously derived forspecific MDP instances. 3) Finally, we show that, in certain "simple" MDPs, thelower bound is considerably smaller than in the general case and it does notscale with the minimum action gap at all. We show that this last result isattainable (up to $poly(H)$ terms, where $H$ is the horizon) by providing aregret upper-bound based on policy gaps for an optimistic algorithm.

A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs