Intelligent user interfaces often rely on modified applications and detailed application models. Such modifications and models are expensive to build and maintain. We propose to automatically model the use of unmodified applications to solve this problem. We observe a user’s interactions with the application’s interface and from these observations deduce a state space which the user navigates and the stochastic policy he or she follows. ONISI, the algorithm presented here, builds this state space implicitly and on-line, and uses it to predict future user actions. Trials with real users show that this algorithm predicts the next user action significantly better than other algorithms.