Learning Sparse Representations in Reinforcement Learning with Sparse Coding
Lei Le Raksha Kumaraswamy Martha White
cs.AI cs.LG stat.ML


Very Large Array multi-band monitoring observations of M 31*
    Yang Yang1,2, Zhiyuan Li1,2, Loránt O. Sjouwerman3, Feng Yuan4,5, Zhi-Qiang Shen4,6
    
=======================================================================================





A variety of representation learning approaches have been investigated for
reinforcement learning; much less attention, however, has been given to investigating the
utility of sparse coding. 













Outside of reinforcement learning, sparse coding representations
have been widely used, with non-convex objectives that result in discriminative representations.
In this work, we develop a supervised sparse coding objective
for policy evaluation. Despite the non-convexity of this objective,
we prove that all local minima are global minima,
making the approach amenable to simple optimization strategies. 
We empirically show that it is key to use a supervised objective, rather than the more
straightforward unsupervised sparse coding approach. 
We compare the learned representations to a canonical fixed sparse representation, called tile-coding,
demonstrating that the sparse coding representation outperforms
a wide variety of tile-coding representations. 




§ INTRODUCTION


For tasks with large state or action spaces, 
where tabular representations are not feasible,
reinforcement learning algorithms
typically rely on 
function approximation.
Whether they are learning the value function, policy or models,
the success of function approximation techniques
hinges on the quality of the representation. Typically,
representations are hand-crafted,
with some common representations including tile-coding,
radial basis functions, polynomial basis functions and Fourier basis functions  <cit.>. 
Automating feature discovery, however, alleviates this burden and
has the potential to significantly improve learning.

Representation learning techniques in reinforcement learning 
have typically drawn on the large literature in unsupervised and supervised learning.

Common approaches include
feature selection, including ℓ_1 regularization on the value function parameters <cit.>
and matching pursuit <cit.>;
basis-function adaptation approaches <cit.>;
instance-based approaches, such as locally weighted regression <cit.>,
sparse distributed memories <cit.>,
proto-value functions <cit.>
and manifold learning techniques <cit.>;
and neural network approaches,
including more standard feedforward neural networks <cit.>
as well as random representations <cit.>,
linear threshold unit search <cit.>,
and evolutionary algorithms like NEAT <cit.>.


Surprisingly, however, there has been little investigation into using sparse coding
for reinforcement learning.

Sparse coding approaches have been
developed to learn MDP models for transfer learning <cit.>;
outside this work, however, little has been explored.
Nonetheless, such sparse coding representations have several advantages,
including that they naturally enable local models, are computationally efficient to use,
are much simpler to train than more complicated models such as neural networks
and are biologically motivated by the observed representation in the mammalian cortex <cit.>.

In this work, we develop a principled sparse coding objective for policy evaluation.
In particular, we formulate a joint optimization over the basis and
the value function parameters, to provide a supervised sparse coding
objective where the basis is informed by its utility for prediction.
We highlight the importance of using the Bellman error or mean-squared return error
for this objective, and discuss how the projected Bellman error is not suitable. 
We then show that,

despite being a nonconvex objective,
all local minima are global minima, under minimal conditions. We avoid the
need for careful initialization strategies needed for previous optimality results for sparse coding 
<cit.>,

using recent results for more general dictionary learning settings <cit.>, particularly by extending
beyond smooth regularizers using Γ-convergence.

Using this insight,
we provide a simple alternating proximal gradient algorithm 
and demonstrate the utility of learning supervised sparse coding
representations versus unsupervised sparse coding and a variety of tile-coding representations.



§ BACKGROUND


In reinforcement learning, an agent interacts with its environment, 
receiving observations and selecting actions to maximize a scalar 
reward signal provided by the environment. 
This interaction is usually modeled by a 
Markov decision process (MDP). 
An MDP consists of (, , P, R) where  is the set of states; 
 is a finite set of actions; 
P: ××→ [0,1], the transition function, which describes the probability of reaching a state 
s' from a given state and action (s,a); and finally the reward function 
R: ××→, which returns a scalar value for transitioning from state-action 
(s,a) to state s'. The state of the environment is said to be 
Markov if Pr(s_t+1 | s_t , a_t) = Pr(s_t+1| s_t , a_t, …, s_0, a_0). 

One important goal in reinforcement learning is policy evaluation: 
learning the value function for a policy.
A value function : →
approximates the expected return. The return G_t from a state s_t is the total discounted future reward, discounted by γ∈ [0,1), 
for following policy
π: ×→ [0,1]


    G_t    = ∑_i=0^∞γ^i R_t+1+i
    = R_t+1 + γ G_t+1


where (s_t) is the expectation of this return from state s_t.

This value function can also be thought of as a vector of values ∈^
satisfying the Bellman equation


    =  + γ
    where    (s,s')    = ∑_a ∈π(s, a) P(s,a,s') 
     (s)    = ∑_a ∈π(s, a) ∑_s' ∈ P(s,a,s') R(s,a,s')


Given the reward function and transition probabilities,
the solution can be analytically obtained: 
= ( - γ)^-1.

In practice, however, we likely have a prohibitively large state space.
The typical strategy in this setting is to use function approximation to learn (s)
from a trajectory of samples:
a sequence of
states, actions, and rewards s_0, a_0, r_0, s_1, a_1, r_1, s_2, r_2, a_2 …,
where s_0 is drawn from the start-state distribution, 
s_t+1∼ P(· | s_t, a_t) and
a_t ∼π(· | s_t). 

Commonly, a linear function is assumed,


(s) ≈(s)^⊤

for ∈^ a parameter vector
and : →^ a feature function
describing states.
With this approximation, however, typically we can no
longer satisfy the Bellman equation in (<ref>),
because there may not exist a  such that 
equals + γ 
for ∈^×.
Instead, we focus on minimizing the error 

to the true value function. 

Reinforcement learning algorithms, such as temporal difference learning
and residual gradient,
therefore focus on finding
an approximate solution to the Bellman equation,
despite this representation issue.
The quality of the representation is critical to accurately approximating 
with , but also balancing compactness of the representation
and speed of learning. Sparse coding, and sparse representations, have proven successful
in machine learning and in reinforcement learning,
particularly as fixed bases, such as tile coding, radial basis functions and other kernel representations. 
A natural goal, therefore, and the one we explore in this work,
is to investigate learning these sparse representations automatically. 



§ SPARSE CODING FOR REINFORCEMENT LEARNING


In this section, we formalize sparse coding for reinforcement learning as
a joint optimization over the
value function parameters and the representation.
We introduce the true objective over all states, and then move to the sampled
objective for the algorithm in the next section.











We begin by formalizing the representation learning component.
Many unsupervised representation learning approaches consist of
factorizing input observations[This variable  can also be a base set of features, 
on which the agent can improve or which the agent can sparsify.] 

∈^× into a basis dictionary ∈^× and 
new representation ∈^×. The rows of  form a set of bases,
with columns in  weighting amongst those bases for each observation (column) in .
Though simple, this approach encompasses a broad range of models, including 

PCA, CCA,
ISOMAP, locally linear embeddings and sparse coding <cit.>.
The (unsupervised) sparse coding objective is <cit.>



    min_∈^×, ∈^× - _D^2 + _F^2 + _D,1


where _F^2 = ∑_ij_ij^2 is the squared Frobenius norm;
∈^× is a learned basis dictionary;
, > 0 determine the magnitudes of the regularizers;
∈ [0,1]^× is a diagonal matrix giving a distribution over states,
corresponding to the stationary distribution of the policy : → [0,1]; and
||||^2_D = ^⊤ is a weighted norm.
The reconstruction error 


    - _D^2 = ∑_s ∈(s) (s,:)  - (s,:) _2^2


is weighted by the stationary distribution  because states are observed with frequency indicated by . 
The weighted ℓ_1 


    _D,1 = ∑_s ∈(s)  ∑_j=1^ |(s,j)|


 promotes sparsity
on the entries of , preferring entries in  to be entirely pushed to zero
rather than spreading magnitude across all of . 
The Frobenius norm regularizer on  ensures that  does not become too large.
Without this regularizer, all magnitude can be shifted to , producing
the same , but pushing _D,1 to zero and nullifying
the utility of its regularizer. 
Optimizing this sparse coding objective would select a sparse representation  for 
each observation  such that  approximately reconstructs .

Further, however, we would like to learn a new representation that is also 
optimized towards approximating the value function. 
Towards this aim, we need to jointly learn  and , where 
provides the approximate value function. In this way, the optimization must balance between accurately
recreating  and approximating the value function .
For this, we must choose an objective for learning .

We consider two types of objectives:
fixed-point objectives and squared-error objectives. 
Two common fixed-point objectives are

the mean-squared Bellman error (MSBE), also called the Bellman residual <cit.>

    - ( + γ) ^2_D

and mean-squared projected BE (MSPBE) <cit.>

    - Π ( + γ) ^2_D


where ∈ [0,1]^× is a diagonal matrix giving a distribution over states,
corresponding to the stationary distribution of the policy;
||||^2_D = ^⊤ is a weighted norm;
and the projection matrix for linear value functions is Π =  (^⊤)^-1^⊤. 
The family of TD algorithms converge to the minimum of the MSPBE, 
whereas residual gradient algorithms typically use the MSBE (see <cit.> for an overview). 
Both have useful properties <cit.>,
though arguably the MSPBE is more widely used. 

There are also two alternative squared-error objectives, that do not correspond to fixed-point equations: 
the mean-squared return error (MSRE) and the Bellman error (BE). 
For a trajectory of samples {(_i, r_i+1, _i+1)}_i=0^-1,
BE is defined as


    ∑_i=0^-1 r_i+1 + γ_i+1^⊤ - _i^⊤_2^2

 
and the MSRE as
 



    ∑_i=0^-1 g_i+1 - _i^⊤_2^2

 
where g_i+1 = ∑_j=i^-1γ^j-i r_j+1 is a sample return. 
In expectation, these objectives are, respectively
 
 
    ∑_s ∈(s) 𝔼[ ( r(S_t,A_t,S_t+1) + γ(S_t+1)^⊤ - (S_t)^⊤)^2 | S_t = s ]
       ∑_s ∈(s) 𝔼[(∑_i=0^∞γ^i r(S_t+i,A_t+i,S_t+1+i) - (s)^⊤)^2 | S_t = s ]

 
 where the expectation is w.r.t. the transition probabilities and taking actions according to policy π. 
 
These differ from the fixed-point objectives because of the placement of the expectation.
To see why, consider the MSBE and BE. The expected value of the BE 
is the expected squared error between the prediction from this state and
the reward plus the value from a possible next state.
The MSBE, on the other hand, 
is the squared error between the prediction from this state and
the expected reward plus the expected value for the next state. 

Though the MSPBE and MSBE constitute the most common objectives chosen for reinforcement learning,
these squared-error objectives have also been shown to be useful particularly for learning online <cit.>.

For sparse coding, 

however, 
the MSPBE is not a suitable choice—compared to the MSBE, BE and MSRE—for two reasons.
First, the MSBE, BE and MSRE are all convex in , whereas the MSPBE is not. 
Second, 
because of the projection onto the space spanned by the features,
the MSPBE can be solved with zero error for any features .










Therefore, because it does not inform the choice of , the MSPBE produces a two stage approach[This problem seems to have been overlooked in
two approaches for basis adaptation based on the MSPBE:
adaptive bases algorithm for the projected Bellman error (ABPBE) <cit.>
and 
mirror descent Q(λ) with basis adaptation <cit.>.
For example, for ABPBE, it is not immediately obvious this would be a problem,
because a stochastic approximation approach is taken. However, if written as a minimization
over the basis parameters and the weights, one would obtain a minimum error solution (i.e., error zero)
immediately for any basis parameters. The basis parameters are considered to change on a slow timescale,
and the weights on a fast timescale, which is a reflection of this type of separate minimization.
<cit.> avoided this problem by explicitly using a two-stage approach, using MSPBE approaches for learning
the parameters and using other score function, such as the squared Bellman error, to
update the bases. This basis learning approach, however, is unsupervised.

Representation learning strategies for the MSPBE have been developed, by using local projections <cit.>. These strategies, however, do not incorporate sparse coding. 


], where 
features are learned in a completely unsupervised way and prediction
performance does not influence .

The final objective for loss L(, ) set to either MSBE, BE or MSRE is


    min_∈^,∈^×, ∈^×   L(, ) +  - _D^2 
       + _2^2 + _F^2 + _D,1










































































§ ALGORITHM FOR SPARSE CODING


We now derive the algorithm for sparse coding for policy evaluation: . 

We generically consider either the BE or MSRE. 
For a trajectory of samples {(_i, r_i+1, _i+1)}_i=0^-1, 












the objective is


    min_∈^,∈^+1 ×, ∈^×1/∑_i=0^-1 ( y_i + γ̅_i+1^⊤ - _i^⊤ )^2 
       + /∑_i=0^_i  - _i_2^2 
     + _F^2
     + _2^2 
     + /∑_i=0^_i ^p_1
    .


for BE, y_i = r_i+1 and γ̅ = γ
and for MSRE,
y_i = ∑_j=i^γ^j-i r_j+1 and γ̅ = 0. 
We consider two possible powers for the ℓ_1 norm p = 1 or 2,
where the theory relies on using p=2, but in practice we find they perform equivalently
and p=1 provides a slightly simpler optimization.

The loss is averaged by , to obtain a sample average, which in the limit converges
to the expected value under . 
This averaged loss is also more scale-invariant—in terms of the numbers of samples—to the choice of regularization parameters.




 consists of alternating amongst these three variables, , and ,
with a proximal gradient update for the non-differentiable ℓ_1 norm.
The loss in terms of  and  is differentiable; to solve for  (or ) with the other variables fixed,
we can simply used gradient descent. 
To solve for  with the  and  fixed, however, we cannot use
a standard gradient descent update because the ℓ_1 regularizer is non-differentiable. 
The proximal update consists of stepping in the direction of the gradient for the smooth component
of the objective—which is differentiable—and then projecting back to a sparse solution
using the proximal operator: a soft thresholding operator. 
The convergence of this alternating minimization follows from results on block coordinate descent
for non-smooth regularizers <cit.>.


To apply the standard proximal operator for the ℓ_1 regularizer,
we need to compute an upper bound on the Lipschitz constant for this objective. 
The upper bound is 2(1+γ̅^2)_2^2 + 2_sp^2,
computed by finding the maximum singular value
of the Hessian of the objective w.r.t. _i for each i. We will provide
additional details for this calculation, and implementation details, in a supplement. 


















 §.§ Local Minima Are Global Minima


In this section, we show that despite nonconvexity,
the objective for  has the nice property that all local 
minima are in fact global minima.
Consequently, though there may be many different local minima,
they are in fact equivalent in terms of the objective. 
This result justifies a simple alternating minimization scheme, where convergence 
to local minima ensures an optimal solution is obtained. 





































































We need the following technical assumption. It is guaranteed to be true for a sufficiently large ≤ (see 
<cit.>).







Assumption 1
For the given ≥, the following function is convex in 𝐙∈^+1 ×+1 



    min_, , , 𝐙 = _F^2 + _2^2 + /∑_i=0^_i ^2_1




For the objective in equation (<ref>) with p = 2, 

1. under Assumption 1, all full-rank local minima are global minima; and

2. if a local minimum (, , ) has _:i = (i.e., a zero column) and _i = 0, _i: = (i.e., a zero row) for some 1 ≤ i ≤, then it is a global minimum. 


For the first statement, we construct a limit of twice-differentiable functions f_n that Γ-converge to
the  objective f. With this, we can then show that all minimizers of the sequence
converge to minimizers of f, and vice-versa <cit.>. 
Because all local minimizers of the twice-differentiable functions f_n
are global minimizers from <cit.>, we can conclude that
all corresponding minimizers of f are global minimizers. 

We use the pseudo-Huber loss <cit.>,
which is twice-differentiable approximation to the absolute value:


|x|_μ = √(μ^2 + x^2) - μ.


Let = (, , ). The sequence of functions f_n are defined with
μ_n = 1/n, as


    f_n() = L() + /∑_ij√(μ_n^2 + _ij^2) - μ_n


where L() equals the equation in (<ref>), but without the ℓ_1^2 regularizer on . 



Part 1: All local minima of f_n for all n are global minima.
To show this, we show each f_n satisfies the conditions of <cit.>.





Part 1.1 


We can rewrite the loss in terms
of 




    1/∑_i=0^-1 y_i + γ̅_i+1^⊤ - _i^⊤_2^2  
    + /∑_i=0^_i  - _i_2^2 
       =
    1/ -  _2^2
    +1/𝐲 -  (_0:-1-γ̅_1:)_2^2


where _1:∈^×+1 a diagonal matrix of all ones with the first diagonal entry set to zero, and _0:-1 with the last diagonal entry set to zero. 


This loss
is convex in the joint variable  because equation (<ref>) is
the composition of a convex function (squared norm) and an affine function (multiplication by γ̅_1: - _0:-1 and addition of 𝐲).

Part 1.2
The regularizer on   must be a weighted Frobenius norm, with weightings on each column;
here, we have weighting using regularization parameters  for the first  columns (corresponding to )
and regularization parameter  for the last column (corresponding to ).

Part 1.3
The inner dimension >, which is true by assumption
and the common setting for sparse coding.

Part 1.4
The pseudo-Huber loss, on the columns of , is convex, centered and twice-differentiable.




Part 2:
The sequence f_n converges uniformly to f. To see why, recall the definition
of uniform convergence. A sequence of functions { f_n } is uniformly convergent with limit f
if for every ϵ > 0, there exists N ∈ such that for all ∈ all n ≥ N,
|f_n() - f()| < ϵ. 
Further recall that for any complete metric space, if f_n is uniformly Cauchy, then it is uniformly convergent.
The sequence is uniformly Cauchy if for all n,m ≥ N, |f_n() - f_m()| < ϵ.

Take any ϵ > 0 and let N = ⌈4 (+1)ϵ⌉. Then 


    |f_n() - f_m()| 
       =  /|( ∑_ij√(μ_n^2 + _ij^2) - μ_n)  -(∑_ij√(μ_m^2 + _ij^2) - μ_m )|
       ≤/∑_ij(| √(μ_n^2 + _ij^2) - √(μ_m^2 + _ij^2)| + | μ_n -μ_m | )


The upper bound of the first component is maximized when _ij = 0, and so we get


    |f_n() - f_m()|    ≤2(+1)| μ_n -μ_m |
    ≤2(+1)| 1n -1m|
       ≤4(+1) N≤ϵ
    .




























Part 3: Asymptotic equivalence of minimizers of f_n and f. 
Because f is continuous, and so lower semi-continuous, and f_n uniformly converges to f,
we know that f_n Γ-converges to f: f_n  f <cit.>. 

By the fundamental theorem of Γ-convergence,
if the { f_n } is an equi-coercive family of functions, then
the minimizers of f_n converge to minimizers of f. 
A sequence of functions { f_n } is equi-coercive iff
there exists a lower semi-continuous coercive function ψ: →∪{ -∞, ∞} such that
f_n ≥ψ on  for every n ∈ <cit.>. A function is coercive if ψ(θ) →∞
as θ→∞. For ψ(θ) = L(), it is clear that ψ is coercive, as well as lower semi-continuous (since it is continuous). Further, f_n() ≥ L() = ψ(), because the regularizer
on  is non-negative. Therefore, the family { f_n } is equi-coercive, and so the minimizers of f_n converge to minimizers of f.

For the other direction, if a local minimum  of f is an isolated local minimum, then there exists a sequence _n → with _n a local minimizer of f_n for μ_n sufficiently small <cit.>.
Because we have Frobenius norm regularizers on ,, which are strongly convex,
the objective is strictly convex with respect to ,. Further, because  is full rank,
 - _F^2 is a strictly convex function with respect to .
 Therefore, locally the objective is strictly convex with respect to . We therefore know that local minima of f are isolated, and so there exists an N such that for all n > N, _n are local minimizers of f_n. Since these local minimizers are global minimizers, 
and they converge to , this means  is a global minimum of f.  



























For the second statement, we use <cit.>. Because we already showed above that our loss can be cast as factorization, it is clear our loss and regularizers are positively homogenous, of order 2. A minimum is guaranteed to exist for our objective, because the loss function is continuous, bounded below (by zero) and goes to infinity as the parameters go to ±∞.
















































§ EXPERIMENTAL RESULTS


We aim to address the question: can we learn useful representations using ? We therefore tackle the setting where the representation is first learned, and then used, to avoid conflating incremental estimation and the utility of the representation. We particularly aim to evaluate estimation accuracy, as well as qualitatively understanding the types of sparse representations learned by . 






























Domains. 
We conducted experiments in three benchmark RL domains - Mountain Car, Puddle World and Acrobot <cit.>. 
All domains are episodic, with discount set to 1
until termination. 


The data in  is generated using the standard energy-pumping policy policy with 10% randomness. 
The data in  is generated by a policy that chooses to go North with 50% probability, and East with 50% probability on each step, with the starting position in the lower-left corner of the grid, and the goal in the top-right corner. 
The data in  is generated by a near-optimal policy.







Evaluation.
We measure value function estimation accuracy using
 mean absolute percentage value error (MAPVE), with rollouts to compute the true value estimates. 
 MAPVE = 1/t_test∑_s∈ X_test|V̂(s) - V^*(s)|/|V^*(s)|, where 
X_test is the set of test states,
t_test=5000 is the number of samples in the test set,
 V̂(s) is the estimated value of state s
 and V^*(s) is the true value of state s computed using extensive rollouts.
 Errors are averaged over 50 runs. 


























Algorithms.
We compare to using several fixed tile-coding (TC) representations. TC uses overlapping grids on the observation space. It is a sparse representation that is well known to perform well for , , and . 

We varied the granularity of the grid-size N and number of tilings D, 
where D is the number of active features for each observation. 

The grid is either N×N for  and  or N^4 for .  
We explore (D=4, N=4), (D=4,N=8), (D=16,N=4), (D=16,N=8), (D=32,N=4), (D=32,N=8); a grid size of 16 performed poorly, and so is omitted.  

For  and   the number of features
respectively  are 64, 256, 256, 1024, 512, 2048, then hashed to 1024 dimensions;
for , the number of features are 1024, 16384, 4096, 65536, 8192, 131072, then hashed to 4096.
Both of these hashed sizes are much larger than our chosen = 100. 



For consistency, once the  representation is learned, we use the same 
batch gradient descent update on the MSRE for all the algorithms, with line search to select step-sizes.  


The regularization weights  are chosen from {1^-5, …, 1^-1, 0}, based on lowest cumulative error. For convenience,  is fixed to be the same as . 
For learning the  representations, regularization parameters were chosen using 
5-fold cross-validation on 5000 training samples, with = 0.1 fixed to give a reasonable level of sparsity.
This data is only used to learn the representation; for the learning curves, the weights are learned from scratch
in the same way they are learned for TC. 


The dimension = 100 is set to be smaller than for tile coding, to investigate if  can learn a more compact
sparse representation. 

We tested unsupervised sparse coding, but the error was poor (approximately 10× worse). 

We discuss the differences between the representations learned by supervised and unsupervised sparse coding below. 

 



Learning curves.
We first demonstrate learning with increasing number of samples, in Figure <ref>. The weights are recomputed using the entire batch
up to the given number of samples.






Across domains,  results in faster learning and, in  and , obtains lowest final error. 
Matching the performance of TC is meaningful, as TC is well-understood and optimized for these domains.
For , it's clear a larger TC is needed resulting in relatively poor performance, whereas  can still
perform well with a compact, learned sparse representation. 
These learning curves provide some insight that we can learn effective sparse representations with , 
but also raise some questions. One issue is that  is not as effective in  as some of the TC representations,
namely 4-4 and 16-4. The reason for this appears to be that we optimize MSRE to obtain the representation, which is a surrogate
for the MAPVE. When measuring MSRE instead of MAPVE on the test data,  consistently outperforms TC.
Optimizing both the representation and weights according to MSRE may have overfitting issues;
extensions to MSBE or BE, or improvements in selecting regularization parameters, may alleviate this issue. 





Learned representations.
We also examine the learned representations, both for unsupervised sparse coding
and , shown in Figure <ref>. We draw two conclusions from these
results: the structure in the observations is not sufficient for unsupervised sparse coding,
and the combination of supervised and unsupervised losses sufficiently constrain the space
to obtain discriminative representations. 
For these two-dimensional and four-dimensional observations, 
it is relatively easy to reconstruct the observations by using only a small subset of dictionary atoms (row vectors of  in equation (<ref>)). The unsupervised representations, even with additional non-negativity constraints to narrow the search space,
 are less distributed, with darker and thicker blocks, and more frequently pick less features.  
 For the supervised sparse coding representation, however, the sparsity pattern is smoother and more distributed: more features are selected by at least one sample, but the level of sparsity is similar. 
 We further verified the utility of supervised sparse coding, by only optimizing the supervised loss (MSRE), without including the unsupervised loss;
 the resulting representations looked similar to the purely unsupervised representations. 
 The combination of the two losses, therefore, much more effectively constrains or regularizes
 the space of feasible representations and improves discriminative power. 





The learning demonstrated for  here is under ideal conditions. This was intentionally chosen
to focus on the question: can we learn effective sparse representations 
using the  objective?
With the promising results here, future work needs to investigate the utility of jointly estimating the representation and learning the value function, as well as providing incremental algorithms for learning the representations and setting the regularization parameters. 




§ CONCLUSION


In this work, we investigated sparse coding for policy evaluation in reinforcement learning.
We proposed a supervised sparse coding objective, for joint estimation
of the dictionary, sparse representation and value function weights. 
We provided a simple algorithm that uses alternating minimization
on these variables, and proved that this simple and easy-to-use approach
is principled. 





We finally demonstrate results on three benchmark domains, Mountain Car, Puddle World and Acrobot,
against a variety of configurations for tile coding.


This paper provides a new view of using dictionary learning techniques from machine learning
in reinforcement learning. It lays a theoretical and empirical foundation for further investigating sparse coding, and other dictionary learning approaches, for policy evaluation and suggests that they show some promise. 
Formalizing representation learning as a dictionary learning problem
facilitates extending recent and upcoming advances in
unsupervised learning to the reinforcement learning setting.
For example, though we considered a batch gradient descent approach for this first investigation,
the sparse coding objective is amenable to incremental estimation, with several works
investigating effective stochastic gradient
descent algorithms <cit.>.
The generality of the approach and easy to understand optimization
make it a promising direction for representation learning in reinforcement learning.






















































named



