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

Partially observable Markov decision processes (POMDPs) have been widelyapplied to capture many real-world applications. However, existing theoreticalresults have shown that learning in general POMDPs could be intractable, wherethe main challenge lies in the lack of latent state information. A keyfundamental question here is how much online state information (OSI) issufficient to achieve tractability. In this paper, we establish a lower boundthat reveals a surprising hardness result: unless we have full OSI, we need anexponentially scaling sample complexity to obtain an $\epsilon$-optimal policysolution for POMDPs. Nonetheless, inspired by the key insights in our lowerbound design, we find that there exist important tractable classes of POMDPseven with only partial OSI. In particular, for two novel classes of POMDPs withpartial OSI, we provide new algorithms that are proved to be near-optimal byestablishing new regret upper and lower bounds.

Theoretical Hardness and Tractability of POMDPs in RL with Partial Online State Information