Category: Reinforcement Learning

Starting today, we will have a RLAI Tea-time talks almost everyday. I do not know how effective this will be; but if it becomes effective (=many good relevant presentations), it can be quite joyful.
I heard from a friend that this idea of tea-time talks comes from Richard Hamming who forces his students to present their research in a similar fashion. However, I doubt about it (I even guess these kinds of things have been existed from the ancient Greek time; imagine Aristotle and Plato talking with each other about the world’s most recent findings (e.g. Archimedes, “Eureka!,” Hellenic Journal of Natural Sciences, 220BC (*)) and Aristotle does not accept vague metaphysical viewpoints of Plato).

(*): Aristotle could not talk about Eureka! paper of Archimedes as this latter one did not publish his paper very soon. Actually, he was born much after those mentioned philosophers.

I have started reading/thinking about this Predictive State Representation (PSR) concept recently. It is interesting in my opinion, but I am not so sure if it is a “really” good thing or not. Anyway, I am investigating it.

I wrote this mail to my friend Mohsen. I guess putting it here may be useful for me and others:

Well … You may ask yourself that why I become interested in SI. The reason is this Predictive State Representation newly proposed concept by a few reinforcement learning researchers. Let me introduce briefly the concept of PSR.

A central problem in reinforcement learning, control engineering, and … is predicting a sequence of observations. You want to know what is the next observation based on what you have seen before. Thereafter, you can design a controller or whatever you want. In order to do so, you need to have a model of the dynamical system.
There are two dominant approaches in modeling dynamical system in RL community. One of them is using Partial Observable MDP (POMDP) and the other is history-based methods. I think you know what a MDP is. MDP is like a dynamical system that you have access to the state information. On the other hand, you do not have access to state information in POMDP, but you observe an output of that system. It is like a dynamical system that you are observing the state of the system through a function of state (y=h(x)).
Well … the bad news, which I believe is common for both RL and control theory, is that it is not reasonable that you have access to the internal model of the dynamics. You may have an approximation of it, but in general, it is not known exactly. The only thing you know for sure is the output (observation) of the system. The whole job of SI is estimating that model. Right now, I want to know if estimation of state-space system is an easy job or not.

PSR is a new idea that wants to remedy this problem. How? It says that instead of modeling an internal dynamics of the system, let’s work only on observations and base our predictions on a set of previous predictions.
Suppose you want to predict (in a stochastic system), the probability of some sequences in the future based on your previous observations. In the language of control theory, it is like predicting the output of a system (in a form of probability distribution) based on its previous responses to signals. The idea of PSR asserts that you can do so if you have a set of known predictions called core tests. For instance, if you know that P{o1o2} = 0.3 and P{o2o3} = 0.5, you can find P{o1o2o3} (it is simplified!) (oi is observation (output) of the system at time instance ‘i’. You know, I used ‘y’ instead of ‘o’ when I was young! (; ). I have some problems with this concept. RL people do not agree that a similar idea exists in other fields. They believe that they are completely new. However, I am not so sure. I think the whole concept is not that new. It may use new names and metaphors, but the concept is like identification of IO systems (identification in the form of transfer function). I think, it is somehow like knowing the impulse response of a linear system. If your system is not linear, the impulse response is not sufficient anymore. But the concept is similar.

Well … what is your idea?! I would be happy if PSR people write me about it.

A few days ago, while sitting in the machine learning class, I was thinking about the following problem about designing a classifier:
AFAIK, In traditional SVM, the goal is maximizing the minimum gap. To cope with noise, we may add slack variables to our constrained optimization programming.
BUT, why don’t we just maximize the total gap (sum of gaps) instead of max. of the min?! This way, outliers act as negative gaps. This problem would be defined as Linear Programming, so we have efficient solution for it.

I just wonder if this approach has been used before. Or is it convertible to some other commonly-used objective functions?

The problem of active learning can be considered as a special case of reinforcement learning (Sanjoy Dasgupta noted it). We can consider it as learning a policy (which selects new data point) that maximizes the increase in some classification performance, e.g. empirical risk, our estimate about structural risk, or anything similar.

Insight into the processes of ‘positive’ and ‘negative’ learners

… their detailed studies also found a difference in ERNs in “positive” and “negative” learners. The former are people who perform better at choosing the correct response than avoiding the wrong one, and the latter are those who learn better to avoid incorrect responses. The negative learners, they found, showed larger ERNs, suggesting that “these individuals are more affected by, and therefore learn more from, their errors. This notion makes the strong prediction that the feedback negativity should also be relatively larger in these participants to negative compared with positive feedback, which could potentially reflect the neural mechanism causing them to be more sensitive to their mistakes.”

Is there two different paths for avoiding something and selecting something? It seems that there are two different mechanism for processing negative and positive experiences. And it seems that it is (at least) due to reinforcement signal generator.

They explained that “In other words, positive reinforcement learners appear to have experienced greater conflict when choosing between two stimuli that were each previously associated with positive (compared with negative) feedback, whereas negative reinforcement learners may have experienced greater conflict when choosing among negative stimuli.”

(maybe) People do some kind of ordering evaluation instead of mere value comparison for their RL-based decisions. And/Or people have different sensitivity in different region of values, i.e. negative values are stored in coarser details comparing with positive values for some people and vice versa.

One common way to evaluate reinforcement learning methods is comparing the learning curve that is usually an average of a few runs (trials) of the method applied to a single problem. If the ultimate part of the learning curve is higher than the other methods, the author says that “our method handles uncertainty and partial observability much better than …”. If the problem is easy enough that reaching the optimal solution is not an astonishing job (e.g. it is MDP), then comparison will be made between slopes of the learning curves, i.e. learning speed. If the method reaches faster to the optimum, it is said that it uses more information during learning/it uses intrinsic hierarchy of the problem better/it bootstraps better/… . Of course, some papers are not written this way, but it is the case.

However, there are a few important points one must pay attention:
1- What if variance of expected gained reward is too high? Averaging a few runs is not very bad, but it is a lossy method of showing results as some very good learning curves can heighten the average curve. This high amount of variance is not due to the intrinsic nature of the problem, but it is due to the fact that the method cannot learn in every run.

To remedy this problem, I am used to plot the probability distribution of the performance instead of mere averaging. This results in a three dimensional diagram (time – performance – probability of the performance) which is not an easy to show on a paper; thus, I do some sampling at different stages of learning and provide a few two dimensional diagram. I do not know whether anyone have used this kind of representation before – but believe me that providing a probability distribution is at least a very good looking diagram! (; But remember to compute “Cummulative Probability Distribution Function” instead of “Probability Density Function”. The latter one is bumpy if you have not many samples.

2- To my best knowledge, there is few mathematical work on the learning speed of RL (I must confess that I have seen two or three papers on the sample complexity of it – but not anymore. There might be a few more). Most researches show the benefit of their method comparing on at most a few problems. Nevertheless, it is not usually said that getting this high performance needs many parameter fine tunings. So, how should we compare two methods when they are not equally optimized?! (Some people used GA or … to find the best learning parameters for their method. I have not done such a thing yet.)

It is in the half time of Brazil-Argentina final match that I get involved in thinking about the decision making process and reinforcement learning. Suppose that one intends to write a program to play soccer. What kind of state representation should he use? The representation must encompass as much information as it is possible to discriminate between two states with different actions (seeing the problem from classification side – separablity classes and …) or it is informative as it enables the agent to separate two state-action pairs with different value (like the abstraction theorem in MaxQ or …).
For instance, the player’s position, the ball’s relative position, and a few nearby players and their tags (opponent/teammate) would be a rational choice. However, one may ask how many nearby players must be selected? Two? Three? More state information you use, the best possible answer to this POMDP would be better. But it is notable that the state representation is exponentially growing with the number of states – at least in most common representations. What should we do?
I guess we must seek for newer (rich) state representation. Here, I am not talking about using general function approximators or hierarchical RL that are useful in their own. I am talking about wise selection of state representation: a dynamic and automatic generation of states is crucial. As an example, suppose that you are a player in the middle of the field and the ball is with your very close opponent (a few meters). The most important factors (read it as state) for your decision making is your relative distance with the opponent and if you are a good player, his limbs’ movement. It is not “that” important to know where the exact position of your teammate is when he is 20 meters away. However, when you are close to the penalty area of the opponent, not only your relative position to your opponents are important, but also your teammate positions might be critical for a good decision making, e.g. passing to your teammate may come at a goal.

I believe that there must be a method for automatic selection of important features for each state. Different states need not have the same kind of representation and dimension. In some situations, the current sensory information might be sufficient, in some other situations, the predictions of other agent’s sensory information might be necessary and … . An extended Markov property may apply to this situation: having a set of S1…Sn (n-dim) state variables, I guess it is possible to reduce the state transition of the MDP environment in this way: P(Si(t+1)..Sj(t+1)..Sk(t+1)|S1(t)…Sn(t)) = P(Si(t+1)..Sj(t+1)..Sk(t+1)|Sp(t)..Sq(t)..Sr(t)) for some p..q..r, i.e. there are some independency here.
As far as I know, the most similar well-known research similar to this idea is work of McCallum: Utile Suffix Memory and Nearest Sequence Memory. Nevertheless, those methods do consider only a single kind of states which is simpler than what I am thinking about.
Well … Brazil won the game tremendously with those samba dancers! Congratulations to Marcelo!

RL is slow?
Large state spaces are hard for RL?!
RL does not work well with function approximation?!
Non-Markovianness invalidates standard RL methods?!
POMDPs are hard for RL to deal with?!
…

In the opinion of Satinder Singh, these are myths of RL. He answers to these myths and expresses that these are not true beliefs. Moreover, there are many other information about reinforcement learning (myths, success, and …) in The University of Michigan Reinforcement Learning Group.