Method to predict action based on previous sequence of actions Given $n-1$ sequences of actions [$k_{i1}$...$k_{in}$] as training/example I want to be able to predict $k_{nn}$ in the sequence [$k_{n1}$...$k_{n(n-1)}$] where $k_{nn}$ would be the most likely action in set $n$ given the previous $n-1$ sets seen.
I first thought of HMM but in my case I would actually be interested in using all my history not just the last k steps.
I've also looked into time series prediction but there is no real connection between the sets of actions only between the elements of the set, so I'm not sure it applies.
What are my best options here?
 A: While this answer may not exactly suit your problem, it might give you a starting point (or others who stumble across this question as I realise you asked this a few months ago):
Have a look at how modern compression algorithms work. Most of them rely on finding patterns in the full history of the data stream. They use these patterns to predict the next symbol. This page has a good discussion of PAQ; an algorithm that is based on prediction using multiple "contexts":

DMC, PPM, and CTW are based on the premise that the longest context for which statistics is available is the best predictor. This is usually true for text but not always the case. For example, in an audio file, a predictor would be better off ignoring the low order bits of the samples in its context because they are mostly noise. For image compression, the best predictors are the neighboring pixels in two dimensions, which do not form a contiguous context. For text, we can improve compression using some contexts that begin on word boundaries and merge upper and lower case letters. In data with fixed length records such as spreadsheets, databases or tables, the column number is a useful context, sometimes in combination with adjacent data in two dimensions. PAQ based compressors may have tens or hundreds of these different models to predict the next input bit.

Rather than selecting just the longest contiguous context as the "winner" which gets to determine the next symbol, context mixing is used in modern prediction algorithms:

Through PAQ3, the weights were fixed and set in an ad-hoc manner. (Order-n contexts had a weight of $n^2$.) Beginning with PAQ4, the weights were adjusted adaptively in the direction that would reduce future errors in the same context set.

...

Mattern (2012) proved that logistic mixing is optimal in the sense of minimizing Kullback-Leibler divergence, or wasted coding space, of the input predictions from the output mix.

Note that many of these algorithms (including PAQ) use a "preprocessor" stage in their compression pipeline which detects the type of file/data and transforms it into a form that's easier to deal with. If you have a look at some of these preprocessors, you'll likely find one that is at least somewhat relevant to your type of data.
And don't get confused by the "coding" phase of data compression - this part isn't relevant to your problem, so no need to explore "arithmetic coding" and other coding stuff you hear about when exploring this field. The compression pipeline is basically: preprocessing --> prediction --> coding and I think you're just concerned with the preprocessing and prediction parts.
Again, not an exact solution for you, but too long to post as a comment, and I thought it might be useful to at least get you started with your specific prediction case.
