In this paper, a hidden Markov model (HMM)-based dynamic sensor scheduling problem is formulated, and solved using information gain and rollout concepts to overcome the computational intractability of the dynamic programming recursion. The problem involves dynamically sequencing a set of sensors to monitor multiples tasks, which are modeled as multiple HMMs with multiple emission matrices corresponding to each of the sensors. The dynamic sequencing problem is to minimize the sum of sensor usage costs and the task state estimation error costs. The rollout information gain algorithm proposed herein employs the information gain heuristic as the base algorithm to solve the dynamic sensor sequencing problem. The information gain heuristic selects the best sensor assignment at each time epoch that maximizes the sum of information gains per unit sensor usage cost, subject to the assignment constraints that at most one sensor can be assigned to a HMM and that at most one HMM can be assigned to a sensor. The roll-out strategy involves combining the information gain heuristic with the Jonker-Volgenant-Castanon˜ (JVC) assignment algorithm and a modified Murty’s algorithm to compute the best assignments at each decision epoch of rollout. The capabilities of the rollout information gain algorithm are illustrated using a hypothetical scenario to monitor intelligence, surveillance, and reconnaissance (ISR) activities in multiple fishing villages and refugee camps for the presence of weapons and terrorists or refugees.