Abstract: An adaptive robust tracking problem is investigated when a discrete-time plant is subject to both unmodelled dynamics and unknown external disturbances. Firstly, combining the l1 optimization and deadbeat control scheme we present a procedure for designing the optimal robust steady tracking controller. Then, based on the idea of set-membership identification, we propose a recursive estimation for extended parameters which include the parameters of nominal model and the bound of unmodelled dynamics and disturbances. Finally, we propose a novel adaptive robust tracking scheme, and prove the overall convergence of the adaptive algorithm. For this scheme a computable tight upper bound on robust tracking performance is also provided. The adaptive scheme proposed in this paper has non-conservative robust stability and asymptotically optimal robust performance.