A Competitive Strategy for Function Approximation in Q-Learning

1 Introduction

It is known that generalization in Reinforcement Learning (RL) is mandatory in applications with large domains [Sutton and Barto, 1998]. Generalization usually involves some kind of Function Approximation (FA) and this is a very challenging problem in RL since, during the learning process, the current estimation of the value function, varies not only as a consequence of the iterative policy evaluation process, where the value function is estimated for the current policy, but also as a consequence of the policy improvement process, which progressively changes the policy towards the optimal one. On the other hand, in incremental RL, data arrive sequentially, following trajectories in the domain dictated by the dynamics of the environment and the current action selection strategy. This causes sampling to be very biased to certain regions, posing a serious difficulty to the FA method to preserve the estimation at sparsely sampled, though also relevant, regions. The non-stationarity problem, and the biased sampling problem usually appear in different degrees at different regions of the domain, and at different stages of the learning process [Boyan and Moore, 1995]. All these problems make the selection of the generalization method a fundamental issue for successful learning.

One way to address the generalization problems is through fitted value iteration [Gordon, 1995], which consists in adjusting the approximation so that the error is minimized on a finite number of preselected domain points that represent the problem sufficiently well. Fitted value iteration takes the data for the given points and tries to fit the function to them by iteratively processing the whole set in a batch process, so that all points get uniformly re-sampled, avoiding the biased sampling problem. Though, in principle, fitted value iteration cannot be considered as an incremental RL method, on-line versions have been proposed like the Neural Fitted Q Iteration (NFQ) [Riedmiller, 2005], in which the set of points is periodically redefined by collecting new samples along trajectories obtained using the policy arrived at so far. Note, indeed, that learning will succeed only if the set of points eventually cover all the relevant parts of the domain, what may be hard to achieve when the dynamics of the problem is not well known. NFQ uses a neural net for function approximation. Other techniques that fall into the fitted value iteration class use Gaussian Processes (GP) for function approximation [Rottmann and Burgard, 2009; Deisenroth et al., 2009; Engel et al., 2005]. They have the advantage of being nonparametric, what makes the class of functions that can be represented much more flexible. In addition, besides providing the expected value of the function, GP also provide its variance, what allows to quantify the uncertainty of the predicted value. As pointed out in [Engel et al., 2005], this information may be very useful to direct the exploration in RL. Similarly, [Agostini and Celaya, 2010] use a Gaussian Mixture Model (GMM) to represent the sample density in the joint input-output space of the function, from which the expected values and their variances can be also obtained. This algorithm, which is not of the fitted value iteration class, uses an on-line Expectation-Maximization algorithm that makes the approach incremental, and tries to solve the biased sampling and the local non-stationarity problems by making the effect of each update sufficiently local.

A more drastic way of keeping the updating local, is that of variable resolution techniques [Moore, 1991], in which the domain is partitioned into regions that are updated independently of each other, and may be further subdivided when their resolution proves to be insufficient. Main drawbacks of this approach are the sometimes unnecessary proliferation of small regions, and the lack of generalization between nearby regions once they have been partitioned.

In this work, we propose the use of many competing function approximators in parallel, each one with a restricted domain, but in which, unlike variable resolution, their domains may overlap in different ways, so that each point is covered by multiple approximators. Trying different approximators in parallel increases the chances of having a good approximator among the competing ones, avoiding the need of adjusting a global approximator complex enough to represent the function in the whole domain. Having approximators with domains of different sizes increases the opportunities to end with the right granularity for generalization, so that the effect of an update reaches distant enough related points, while keeping far away unrelated regions unaffected. An important aspect of this approach is the selection of the competitor that will be used to determine the function value at each point of the domain. For this, a relevance function is computed for each competitor, taking into account its expected accuracy and confidence at each point. The competitor that has the highest relevance in a given point is used to provide the value at this point. Using this approach for Q-learning would require, in principle, the estimation of three functions for each competitor: one for the q-value, one for the accuracy, and a third one for the confidence at each state-action point. Fortunately, we can obtain estimations of all these functions from a unique probability density function in the joint space of states, actions, and values. Thus, from the joint probability density, we can obtain the q-value function simply as the mean of the q-value conditioned to a given state-action; the accuracy will be obtained using the conditioned variance of this q-value; and the confidence will be obtained using the sample density in the state-action space. According to this, we will approximate a single joint density function for each competitor by means of a GMM, for which an efficient updating EM algorithm can be used. In the next Section we formally define the competitor system and the relevance function. In Section 3, the implementation of the system using Gaussian Mixture Models is presented, and in Section 4 its application to Q-learning is explained. Section 5 describes the experiments carried out to demonstrate the validity of the approach, and Section 6 closes the paper with some conclusions.

2 Competitive Function Approximation

This section presents the formalization of a function representation using a competitive strategy that will be used for the approximation of an arbitrary target function.

We define a competitor function, Φi(x, ξi), as a parametric function with parameters ξi, defined on values x of a Ddimensional continuous domain Xi. Associated with each competitor Φi, there is a relevance function, Γi(x, νi), which is a parametric function with parameters νi, also defined in the domain Xi.

Given a set of competitors Φ = {Φ1,Φ2, . . . ,Φ|Φ|}

and the set of their corresponding relevance functions Γ = {Γ1, Γ2, . . . , Γ|Φ|}, we consider the function, y =

F(x, Φ, Γ), for x ∈ X = |Φ| ⋃ i=1 Xi, defined as follows: First, a

winner competitor, Φw, is selected such that

where Ix = {i|x ∈ Xi} references the set of active competitors for x, Φx = {Φi|x ∈ Xi}. Then the value y is obtained as,

Now, assume that there is an arbitrary unknown target function f(x) defined in X that should be approximated, but from which we can only observe its values at particular points obtained sequentially, (xt, yt), with yt = f(xt), where t accounts for the t-th time step. Our aim is to devise an online (i.e., incremental), memory-free function approximation method using a function F(x,Φ,Γ) as defined before. To this end we need to specify the functions that will be used as competitors Φi(x, ξi), their respective relevance functions Γi(x, νi), and the method that will be used to update the parameters ξi and νi in order to get a good approximation of the target function, so that:

We call a method for function approximation that uses a function F(x, Φ, Γ) a competitive function approximation (CFA) method.

For the competitors Φi(x, ξi) of a CFA system, we can use any set of arbitrarily complex parametric functions and, in principle, they do not need to be all the same. However, in the following, we will assume that all competitors implement the same function of its parameters: Φi(x, ξi) = Φ(x, ξi). It will be convenient to choose as Φ(x, ξi) some function for which an efficient incremental updating method for function approximation is available, so that we can use it for updating the parameters ξi. The type of function selected and the extension of the domains of each competitor will influence the possibilities of generalization of the CFA. However, if the relevance function is not able to provide a correct distinction between good and bad approximations, the performance of the CFA system will be poor, no matter what competitor function is used. Hence, a right definition of the relevance function is crucial for the good performance of the CFA system. The next section is focused on this aspect.

2.1 Relevance Function

To make the exposition clear we assume first that the competitor and the relevance functions are constant-valued functions of x. They can be seen as uniparametric functions where the parameter ξi corresponds to the constant value assigned by the function. In this case, the sample mean of the observed values in each domain is a clear choice for the parameter of the corresponding approximator,

where ni is the total number of samples observed so far in Xi. To define the relevance function, note that the variance of f in Xi, σ2 i = EXi [(f(x) -EXi [f(x)])2 ], is a good indicator of how well EXi [f(x)] (≈ ¯ Yi) approximates f in x. Hence, the inverse of the variance σ2 i would be a good value for the relevance. However, as we only have a limited amount of samples of f(x), its variance can not be determined precisely and should be estimated. We estimate the variance using the (unbiased) sample variance S 2 i :

The uncertainty of this estimation depends on the number of samples ni and to take into account this uncertainty we use the upper bound of the confidence interval for the variance [Blom, 1989]:

where χ2α (ni - 1) is the α-quantile of a χ2 distribution, with ni - 1 degrees of freedom. This upper bound represents the highest possible value (with α confidence) of the actual unknown variance given the current uncertainties in the estimation. Less confident estimations will have higher upper bounds for the variance. The value (6) provides a measure of the quality in the approximation that balances the estimation accuracy and the confidence in that estimation. Hence, we can adopt the inverse of the upper bound of the confidence interval for the variance as the relevance of a competitor Φi:

This definition of the relevance prevents competitors with estimations obtained from a few samples, but showing low variances, to be favoured in front of those with slightly higher variances but with much more confident estimations.

Until now, we have assumed constant-valued estimations for the competitor and the relevance functions but, in general, they will depend on x. For the relevance to be x-dependent, the estimation of the variance and its confidence must also be x-dependent. Thus, assuming that the sample variance is approximated by some parametric function S 2 i (x, τi), we can estimate the sample variance ˜ S 2 i for samples experienced in a region ˜Xi ⊂ Xi as

where pi(x, ςi) is a parametric estimation of the sample probability density function in Xi. In a similar way, we can estimate the number of samples in ˜Xi as:

Now, replacing the sample variance and the number of samples in Xi in (7) by their respective counterparts in ˜Xi, we can express the relevance function of competitor i in a point x ∈ ˜Xi as

With this relevance formula we can regulate the precision of the relevance of a competitor at a point x by adjusting the size of the region ˜Xi to an appropriate value depending on the nature of the generalization performed and the regularity of the variance function. In order to simplify the calculations of the integrals in (8) and (9), we assume that the region ˜Xi is small enough for the values for the probability density function pi(x, ςi) and the variance function S 2 i (x, τi) to be nearly constant, which permits to estimate the relevance (10) as

where ˜ Vi is the volume of ˜Xi. In practice, the volume ˜ Vi is defined empirically for each particular problem.

3 Competitive Function Approximation with Gaussian Mixture Models

In this section we present the specific instantiation of the method for CFA that we will use for generalization in RL. We need to specify the competitor functions Φi(x, ξi), as well as the variance functions S2 i (x, τi), and the density functions pi(x, ςi) needed to calculate the relevance (11). In addition, we also need to provide the mechanisms to update all the parameters involved. Next, we just give a general description of the approach. A more detailed explanation can be found in [Agostini and Celaya, 2010].

For the instantiation of each competitor function we will use a Gaussian Mixture Model (GMM) defined in the inputoutput joint space,

where z = (x, y) is the input-output variable; K is the number of Gaussians of the mixture; αj, usually denoted as the mixing parameter, is the prior probability, P(j), of Gaussian j to generate a sample; N(z; μj,Σj) is the multidimensional Gaussian function with mean vector μj and covariance matrix Σj; and Θ = {{α1, μ1,Σ1}, ..., {αK, μK,ΣK}} is the whole set of parameters of the mixture. This representation has the virtue of providing an approximation of the value function as well as all the quantities required in (11) from a single density model. Thus, by embedding a probability density model pi(z; Θi) at each competitor Φi, we can easily derive, through the conditional probabilities, a point-dependent estimation of the sample mean,

as well as a point-dependent estimation of the sample variance,

In addition, from the density model we can estimate the number of samples involved in the estimation of the mean and variance at each point,

where pi(x;Θi) is the probability density estimation in the input space. The parameters Θi are updated from each incoming experience (xt, yt), using the incremental version of the Expectation-Maximization algorithm proposed in [Agostini and Celaya, 2010].

3.1 Competitor Management

The set of competitors of a CFA must be defined so that their domains Xi form a covering of the whole domain X. Since it is not possible, in general, to determine beforehand the best way to define the number and sizes of the Xi's, we start with an initial covering with a relatively small number of competitors and, in the course of learning, new competitors are generated as required by the need of a better approximation. This makes the approach non-parametric and, in principle, able to approach any arbitrary function. We would like to note that it is also possible to make the approach non-parametric by changing not only the number of competitors but also the number of Gaussians at each competitor. However, we will keep the number of Gaussians fixed, varying only the number of competitors.

Our criteria for competitor generation involves two userdefined thresholds: ng, which sets the minimum number of samples that should be collected by a competitor before its estimations can be considered confident, and eg, which sets the maximum error allowed in the approximation. New competitors will be generated when, after observing a new sample (x, y), the approximation error is too large,

and all the active competitors for x have reached the minimum confidence threshold:

This last condition is necessary to avoid the generation of further competitors in a region where one has already been generated but has not yet been updated enough to adjust its parameters.

When these two criteria are fulfilled, a new competitor domain is generated by intersecting that of the winner competitor at x, Xw, with the domain of the competitor that showed the least prediction error at the sampled point. If this domain is different from all the already existing Xi, a new competitor is generated with it. In the case that a competitor with such domain already exists, it makes no sense to generate it again, so that, in this case, new domains are built by splitting that of the winner, Xw, in three overlapping subdomains, each one of half the size of Xw. Each subdomain is obtained by appropriately cutting Xw along the dimension d along which the dispersion of samples of Xw is the largest (i.e., the dimension whose marginal variance is maximum for the winner competitor). Generation via splitting complements the generation via intersection of existing domains, since it permits to increase the resolution indefinitely, which is not possible by intersections alone.

Each new competitor is initialized with a Gaussian Mixture Model with K Gaussians with initial mean vectors (x, y) = (xr,Φw(xr, ξw)), where the input points xr are selected at random from the domain of the competitor. The covariance matrices are initialized to diag{d21 , ..., d2D , S2w(xr, τw)}, where dj is a fixed percentage of the length of the domain in the j dimension, andD is the dimension of the input space. In the cases in which the new domain contains the experienced input xt, it is taken as one of the xr, and the sample point (xt, yt) is taken as the mean of the corresponding Gaussian.

Elimination of Competitors

The competitors that become less useful for the system can be eliminated. We remove those competitors that are redundant with others. We say that a competitor Φi is redundant with a competitor Φj when

and the normalized differences in their values and relevances are both below some thresholds for all x ∈ Xi:

and

In practice, these conditions are tested only in a finite number of points of Xi. These tests are performed between overlapping competitors once every fixed number of samples.

4 Q-Learning with a CFA

Next, we explain how the CFA just described can be used with Q-learning in continuous state and action spaces. The function to be approximated is the utility function Q(s, a). The input points x correspond to state-action pairs (s, a), and the function values y will be the current estimation q(s, a) of the real Q(s, a) function, obtained from the sampled version of the Bellman equation:

where r(s, a) is the immediate reward obtained after executing action a in state s; s′ is the state observed after the action execution; and ˆQ(s′ , a′ ) is the approximation of the action-value function at (s′ , a′ ) provided by the CFA system: ˆQ(s′ , a′ ) = F((s, a), Φ, Γ)) = Φw(s′ , a′ ).

To compute the value q(s, a) we need to solve the maximization problem max a′ ( ˆQ(s′ , a′ )). We adopt the strategy of computing the values ˆQ(s′ , a′ ) for a finite number of actions, and then taking the value of the action that provides the largest Q as the approximated maximum.

For action exploration we follow the strategy proposed in [Agostini and Celaya, 2010], assigning to each (s, a) to be evaluated a value calculated randomly as,

where ΔQ(σ2 (q|s, a)) is a value taken at random from a normal probability distribution with 0 mean and variance σ2 (q|s, a) = S 2w((s, a), τw). Once a Qrnd(s, a) value has been assigned for every evaluation (s, a), the action to be executed is selected using the greedy policy as,

5 Experiments

To demonstrate the performance of the CFA in Q-Learning we use two different benchmarks: the pendulum swing-up and stabilization [Doya, 2000], and the cart-pole balancing [Sutton and Barto, 1998]. The first task consists in swinging the pendulum until reaching the upright position and then stay there indefinitely. The pendulum model is the same used in [Doya, 2000] with a reward given by the height of the pendulum. Training and test episodes consist in 50 seconds of simulated time, with an action interval of 0.1 seconds. The second task, the cart-pole balancing, consists in a pole mounted on cart that has to be stabilized inside an acceptable region by the motions of the cart. The cart is free to move in an acceptable range within a 1-dimensional bounded track, and the pole moves in the vertical plane parallel to this track. The cart-pole benchmark is of interest since it involves a 5dimensional state-action space, two more than the inverted pendulum, and serves to illustrate the scalability of the algorithm. The set-up for the experiment is the same used in [Peters and Schaal, 2008], with a reward function that varies linearly from 0 at the bound of the acceptable angle for the pole, to 1 at the vertical position. Reward is -1 when either the pole or the cart leave their acceptable regions.

For both benchmarks, we give results using three different function approximation techniques: the GMMwith variable number of Gaussians of [Agostini and Celaya, 2010], the CFA introduced here, and Variable Resolution, to provide a general reference. Table 1 shows the parameters for CFA used in both benchmarks.

5.1 Results

Figures 1 and 2 show the results of the experiments, that in all cases are the average of 15 independent runs of each algorithm. In both benchmarks, the GMM and CFA approaches are clearly superior to Variable Resolution. For the pendulum swing-up task, we show the performance of the GMM approach with two different initializations: One with 10 Gaussians, that reported the best results in [Agostini and Celaya,

2010], and another with 100 Gaussians, what corresponds to the same total number of initial Gaussians of our approach with CFA. Figure 1 shows that CFA has a faster and more stable convergence than both instantiations of the GMM. For the case of 10 initial Gaussians, GMM reaches a stable value in about 45 episodes, while CFA does the same in about 23. For the GMM with 100 initial Gaussians the performance is worst, likely due to the fact that the system must simultaneously balance a large number of parameters (in fact, 100 Gaussians is more than required, since the GMMwith 10 initial Gaussians reaches convergence with an average of about 45 Gaussians). Increasing the number of competitors, and therefore the total number of Gaussains, has not the same effect in CFA, since each competitor must only balance their own parameters, independently of those of other competitors (convergence is achieved with 185 competitors in average). To give a comparison of these results with the state of the art on this benchmark, we recall the results given by [Riedmiller, 2005] for this task, where, using a batch NFQ algorithm, reports convergence after 100.000 × D updates (D = number of samples), while GMM takes about 45 × 500 = 22.500 updates, and CFA only 23 × 500 = 11.500.

In the case of the cart-pole, the different performance between the three approaches is even larger, as shown in figure 2. We attribute the superiority of GMM and CFA over VR to their better generalization capabilities, which become more important as the dimensionality of the state-space increases. To interpret the much better performance of CFA over GMM in this benchmark, we note that GMM required, in average, a final amount of 190 Gaussians to reach convergence, while CFA required, in average, about 445 competitors with only 20 Gaussians each. Thus, even if the total number of Gaussians in CFA is much larger, many competitors are updated in parallel at each iteration, and each of them has to adjust a much smaller set of parameters. To compare these results with the state of the art, we observe that CFA reaches a good performance after about 3 minutes of simulated time and converges in less that 5 minutes, while [Peters and Schaal, 2008], using a Natural Actor-Critic approach, reported convergence after 10 minutes.

6 Conclusions

The results obtained in this work support our claim that it is advantageous to use a collection of function approximators defined on overlapping regions of the whole domain that compete between them to provide the best estimation at each point, instead of using a single global approximator of arbitrary complexity. There are several reasons that may explain this. One is locality: since each approximator is only updated with those samples that fall in its domain, it is not influenced by farther away samples, thus avoiding most of the overfitting problems caused by the biased sampling usually found in reinforcement learning. Another reason is that covering the domain with regions of different sizes, it is possible to find the right one where the complexity of the target function matches the approximation capabilities of the competitors. An optimal match between the complexity of the target function and the approximator gives rise to a maximally efficient learning and accurate generalization. Being able to choose the more plausible (or relevant) competitor at each point makes possible to keep inaccurate competitors in the system without distorting the accuracy of the actual approximation.

Still another reason that makes the competitive approach attractive in reinforcement learning is its capability to deal with non-stationary target functions: when a drastic change of the target function occurs at some point of the domain, it is not necessary that the formerly winner competitor at this point completely reshape its approximation before the output becomes accurate; instead, a different competitor that managed to be more accurate at that point will provide the output as soon as its relevance gets larger there.

As expected, the computational cost of the CFA method is higher than that of the single global GMMmethod. However, in the presented experiments, the increase in computation time is less than one order of magnitude.

Acknowledgments

This research was partially supported by Consolider Ingenio 2010, project CSD2007-00018.