This paper presents an optimal model-free solution to the output synchronization of heterogeneous multi agent discrete-time systems. First, local discounted performance functions are defined for all agents and the optimal synchronization control protocols are found by solving a set of algebraic Riccati equations (AREs) and without requiring the explicit solution to the output regulator equations. It is shown that the proposed method implicitly solves the output regulator equations and therefore solves the output synchronization problem, provided that the discount factor is bigger than a lower bound. This formulation enables us to develop a Q-learning algorithm to solve the AREs using only measured data and so find the optimal distributed control protocols for each agent without requiring complete knowledge of the agents' or leader's dynamics. It is shown that the combination of a distributed adaptive observer and the controller guarantees synchronization. The relationship between the standard solution and the proposed solution is also shown. A simulation example is given to show the effectiveness of the proposed method. (C) 2017 Elsevier Ltd. All rights reserved.