Extreme State Aggregation beyond MDPs
By Marcus Hutter. 2014
23 citations recorded by the source corpus.
We consider a Reinforcement Learning setup without any (esp. MDP) assumptions on the environment. State aggregation and more generally feature reinforcement learning is concerned with mapping histories/raw-states to reduced/aggregated states. The idea behind both is that the resulting reduced process (approximately) forms a small stationary finite-state MDP, which can then be efficiently solved or learnt. We considerably generalize existing aggregation results by showing that even if the reduced process is not an MDP, the (q-)value functions and (optimal) policies of an associated MDP with same state-space size solve the original problem, as long as the solution can approximately be represented as a function of the reduced states. This implies an upper bound on the required state space size that holds uniformly for all RL problems. It may also explain why RL algorithms designed for MDPs sometimes perform well beyond MDPs.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Nan Jiang
- Tom Everitt
- Sergey Levine
- Doina Precup
- Marcus Hutter
- Khimya Khetarpal
- Michael L. Littman
- David Abel
Citations in the corpus
- Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “It is known that certainty-equivalence with Q ⋆ -irrelevant abstraction is consistent and enjoys polynomial sample complexity when each state-action pair receives enough data (Li, 2009; Hutter, 2014; Jiang et al., 2015; Abel et al., 2016; Jiang, 2018).”
- Near Optimal Behavior via Approximate State Abstraction (2016, unknown): “ 1norm, which parallels our Claim 2. Ortner [27] developed an algorithm for learning partitions in an online setting by taking advantage of the condence bounds for Tand Rprovided by UCRL [3]. Hutter [18, 17] investigates state aggregation beyond the MDP setting. Hutter presents a variety of results ”
- Self-Modification of Policy and Utility Function in Rational Agents (2016, background): “Most of the following notation is by now standard in the general reinforcement learning (GRL) literature (Hutter, 2005, 2014).”
- Value Preserving State-Action Abstractions (2020, background): “Indeed, prior work has illustrated the potential for abstractions to support both this first (Konidaris and Barto, 2007; Brunskill and Li, 2014; Bacon et al., 2017) and second property (Li et al., 2006; Van Roy, 2006; Hutter, 2014).”