Approximate Equivalence of Markov Decision Processes

By Eyal Even-Dar, Yishay Mansour. 2003

43 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Information-Theoretic Considerations in Batch Reinforcement Learning (2019, methodology): “…space of piece-wise constant functions under a partition induced by state abstraction φ , the notion of completeness (Assumption 3, F = G ) is exactly equivalent to a long-studied type of abstractions, known as bisimulation (Whitt, 1978; Even-Dar & Mansour, 2003; Ravindran, 2004; Li et al., 2006).”
State Abstractions for Lifelong Reinforcement Learning (2018, methodology): “For instance, in the exact setting, one commonly studied predicate is deﬁned as follows: In the approximate relaxation, the predicate is deﬁned with a small constant ε ∈ [0 , VM AX ] : In general, computing the approximate state abstraction that induces the smallest possible abstract state space for”
Abstraction Selection in Model-based Reinforcement Learning (2015, background): “When the quality of the abstraction is known, the theory of approximate homomorphisms in MDPs bounds the loss of the certainty equivalence policy (Even-Dar & Mansour, 2003; Ravindran, 2004).”
Toward Good Abstractions for Lifelong Learning (2017, background): “This is a dramatic reduction in computational complexity relative to the previous NP-Hardness result.”
Towards a Unified Theory of State Abstraction for MDPs (2006, background): “One possible extension is to relax the exactness and allow some form of approximate or soft abstraction [5, 7, 8].”
Near Optimal Behavior via Approximate State Abstraction (2016, background): “Even-Dar and Mansour [13] analyzed diﬀerent distance metrics used in identifying state space partitions subject to ε -similarity, also providing value bounds (their Lemma 4) for ε -homogeneity subject to the L ∞ norm, which parallels our Claim 2.”
Bisimulation Metrics for Continuous Markov Decision Processes (2011, background): “In the paper of Even-Dar and Mansour [23], this work was expanded upon by considering different norms on the probability parameter in the definition of -homogeneity and providing performance results specifically showing that the quality of an -homogeneous partition depended heavily on the norm in us”
Agent-Agnostic Human-in-the-Loop Reinforcement Learning (2017, methodology): “Other methods have focused on state abstraction functions to decrease learning time and preserve the quality of learned behavior, as in [26, 33, 12, 20, 7, 3, 13].”
A unifying framework for computational reinforcement learning theory (2009, background): “A regret lower bound of Ω(lnH) in K-armed bandits has been known for a long time. Lai and Robbins [1985] show an algorithm that achieves this lower bound asymptotically.”