Cognitive radios, which enable the coexistence on the same bandwidth of licensed primary and unlicensed secondary users, have the potential for dramatically increasing the efficiency of wireless networks. In this paper, we propose an on line learning algorithm to optimize the transmission strategy of secondary users in interference mitigation scenarios, where the secondary users are allowed to superimpose their transmission onto those of the primary users. Due to practical imitations, the secondary users have access to only a fraction of the current state of the primary users'' network. Therefore, the strategy of the secondary users is defined on a reduced state space. Numerical results show that the proposed practical learning algorithm operates close to the performance of the system under full knowledge.