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

Reinforcement Learning (RL) encompasses diverse paradigms, includingmodel-based RL, policy-based RL, and value-based RL, each tailored toapproximate the model, optimal policy, and optimal value function,respectively. This work investigates the potential hierarchy of representationcomplexity -- the complexity of functions to be represented -- among these RLparadigms. We first demonstrate that, for a broad class of Markov decisionprocesses (MDPs), the model can be represented by constant-depth circuits withpolynomial size or Multi-Layer Perceptrons (MLPs) with constant layers andpolynomial hidden dimension. However, the representation of the optimal policyand optimal value proves to be $\mathsf{NP}$-complete and unattainable byconstant-layer MLPs with polynomial size. This demonstrates a significantrepresentation complexity gap between model-based RL and model-free RL, whichincludes policy-based RL and value-based RL. To further explore therepresentation complexity hierarchy between policy-based RL and value-based RL,we introduce another general class of MDPs where both the model and optimalpolicy can be represented by constant-depth circuits with polynomial size orconstant-layer MLPs with polynomial size. In contrast, representing the optimalvalue is $\mathsf{P}$-complete and intractable via a constant-layer MLP withpolynomial hidden dimension. This accentuates the intricate representationcomplexity associated with value-based RL compared to policy-based RL. Insummary, we unveil a potential representation complexity hierarchy within RL --representing the model emerges as the easiest task, followed by the optimalpolicy, while representing the optimal value function presents the mostintricate challenge.

Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity