In multi-agent environments, the task of agent track-ing (i.e., tracking other agents’ mental states) in-creases in difficulty when a tracker (tracking agent)only has an imperfect model of the trackee (trackedagent). Such model imperfections arise in many real-world situations, where a tracker faces resource con-straints and imperfect information, and the trackeesthemselves modify their behaviors dynamically. Whilesuch model imperfections are unavoidable, a trackermust nonetheless attempt to be adaptive in its agenttracking. In this paper, we analyze some key issuesin adaptive agent tracking, and describe an initial ap-proach based on discrimination-based learning. Themain idea is to identify the deficiency of a model basedon prediction failures, and revise the model by usingfeatures that are critical in discriminating successfuland failed episodes. Our preliminary experiments insimulated air-to-air combat environments have shownsome promising results but many problems remainopen for future research.