Basis Function Discovery using Spectral Clustering and Bisimulation Metrics (Extended Abstract)

Markov Decision Processes (MDPs) are a powerful framework for modeling sequential decision making for intelligent agents acting in stochastic environments. One of the important challenges facing such agents in practical applications is finding a suitable way to represent the state space, so that a good way of behaving can be learned efficiently. In this paper, we focus on learning a good policy when function approximation must be used to represent the value function. In this case, states are mapped into feature vectors, and a set of parameters is learned, which allows us to approximate the value of any given state. Theoretically, the quality of the approximation that can be obtained depends on the set of features. In practice, the feature set affects not only the quality of the solution obtained, but also the speed of learning. We focus on learning feature vectors in fully specified MDPs by a set of states S, a set of actions A, a transition model P : S × A × S → [0, 1], and a reward function R : S × A → [0, 1]. Also, γ is a discount factor and γ ∈ (0, 1). A policy π : S × A → [0, 1] specifies a way of behaving for the agent, and we would like to evaluate the long term behavior it generates. We do this using the value function, which is defined (using matrix notation) as V = ∑∞ i=0(γπP ) (πR) = π(R + γPV ). The last equality is known as the Bellman equation, and is at the heart of most incremental sampling algorithms to find V . Our goal is to linearly approximate intermediate computations Cite as: Basis Function Discovery using Spectral Clustering and Bisimulation Metrics (Extended Abstract), Gheorghe Comanici, Doina Precup, Proc. of 10th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2011), Tumer, Yolum, Sonenberg and Stone (eds.), May, 2–6, 2011, Taipei, Taiwan, pp. 1079-1080. Copyright c © 2011, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved. of V ≈ Φθ, where Φ maps every state to feature vectors of dimension much smaller than |S|, and attempt to minimize ||V − Φθ||2. Two types of methods have been proposed in recent years to tackle this problem. The first category of methods aims to construct basis functions that reduce the error in value function estimation[3, 5]. In this case, features are rewardoriented, and are formed with the goal of reducing value function estimation errors. The second approach, exemplified by the work of Mahadevan and Maggioni [4] (and their colleagues) relies on using data to construct a state connectivity graph. Spectral clustering methods are then used to construct state features. The resulting features capture interesting transition properties of the environment (e.g. different spatial resolution) and are reward-independent. That is, the features generated are eigenvectors of the Normal-

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.