Markov decision process in R for a song suggestion software? We have a music player that has different playlists and automatically suggests songs from the current playlist I'm in. What I want the program to learn is, that if I skip the song, it should decrease the probability to be played in this playlist again. I think this is what's called reinforcement learning and I've read a bit about the algorithms, deciding that Markov decision process (MDP) seems to be exactly what we have here. I know that in MDP there is more than one state, so I figured for this case it would mean the different playlists. For example, depending on the state (playlist) I'm in, it chooses the songs that it thinks fits the best and get "punished" (by skipping) if it has chosen wrongly.  
Do you guys think this is the right approach? Or would you suggest a different algorithm? Does all of this even make any sense, should I provide more information?  
If it does sound right, I'd like to ask for some tutorials or starting points getting about MDP in R. I've searched online but have only found the MDP toolbox in R and it kind of doesn't really make sense to me. Do you have any suggestions? 
 A: This question is months old now but it's still interesting. To me this sounds like a massive contingency table or sparse data, tensor problem. This doesn't make any of the MDP or reinforcement learning issues moot, it just realigns the statistical framework within which they are modeled.
The decision or dependent variable is whether or not a song from a potentially very large playlist gets chosen and, once chosen, whether it gets rejected or played. Correct me if I'm wrong, but can't this be treated with effect coding or 0, 1 for yes/no -- is it played? -- and -1 if it's rejected? 
Based on the question, I don't see any reason to treat this as a sequential Markov chain or longitudinal time series, particularly given the random nature of the draws from the playlist, but can be convinced otherwise. Exceptions to this rule could include consideration of whether the algorithm is "learning" song preferences as a function, for instance, of genre. 
Sparsity would be a function of the interval for the time frame over which the choices are aggregated as well as the size of the playlist. If the interval is too short or the playlist is too large, sparsity is the inevitable outcome.
The state-of-the-art for tensor modeling are probably David Dunson's papers, e.g., Bayesian Tensor Regression, but there are lots of people with plenty of papers working in this field (see DDs papers on his Duke website for reviews).
A: The problem can be modeled as Markov Decision problem. I have tried to fit the problem in MDP framework, let me know if this is of any help.
Assuming that there exists a method to select a song within a playlist 'cluster', the states would act as such clusters for MDP.
Defining a transition probability matrix between clusters, actions by MDP would be a change in this matrix. Here, app user inputs would act as external disturbances in the model. The reward/cost model would depend on these external disturbances.
In summary,
States: Playlist clusters 
Actions: Updates in transition probability matrix
Disturbances: App user inputs as accept/reject the song
Cost function: Stochastic output on whether a user would accept/reject next few suggestions
An extension would be to simulate user behavior as a stochastic process, and infer the parameters based on actual data.
A: It is right that there is a Reinforcement Learning problem here. The negative reinforcement would be when the person skips the song, and positive when he/she doesn't. The action in this case would be choosing the song, and you wanted the state to be a playlist. I don't think this is a good idea. First, you'd have a varied number of songs (thus actions) per playlist (state) which doesn't make much sense.
I would generalise it a bit:


*

*state: for example the person's mood or music preference of the person.

*action: choose a type of music / artist for example. 

*reward: negative when skipped, otherwise 0 or positive.


This way the method is more generic, and the meta data (music type, artist, ..) can easily be extracted from a MP3 file for example.
I have not used any R package with MDPs, but this link seems interesting:
Reinforcement Learning in R: Markov Decision Process (MDP) and Value Iteration
