Sequence Similarity for Hidden State Estimation

Little work has been done on comparing long- and short-term memory (LTM and STM) traces in the context of hidden state estimation in POMDPs.  Belief-state algorithms use a probabilistic step-by-step approach which should be optimal, but doesn't scale well and has an unrealistic requirement for knowledge of the state space underlying observations, 

The instance-based Nearest Sequence Memory (NSM) algorithm performs remarkably well without any knowledge of the underlying state space.  Instead is compares previously observed sequences of observations and actions in LTM with a recently observed sequence in STM to estimate the underlying state.  The NSM algorithm uses a count of matching observation-action records as a metric for sequence proximity.

In problems where certain observation-actions are particularly salient, e.g., passing through a 'door' in Sutton's world, or picking up a passenger in the Taxi problem, a simple match count is not a particularly good sequence proximity metric and, as a result, I have recently been casting around for other work on such metrics.

ADD SLTM work reference here.

I have come across some interesting work on sequence comparison by Z. Meral Ozsoyoglu, Cenk Sahinalp and Piotr Indyk on Improving Proximity Search for Sequences.  This work has been done in the context of genome sequencing could be an interesting starting point for going beyond the simple match count metric used by NSM.