Learning Near-Pareto-Optimal Conventions in Polynomial Time

We focus on repeated coordination games of non-identical interest where agents do not know the game structure up front and receive noisy payoffs. We design efficient near-optimal algorithms forboth the perfect monitoring and the imperfect monitoring setting(where the agents only observe their own payoffs and the joint actions).