We consider a system of N agents, picking actions from a finite set and receiving payoffs depending on actions of all. The payoffs form is unknown and only their values can be measured by agents. A decentralized algorithm was proposed by Young and in authors’ earlier work, that leads to the agents picking welfare optimizing actions. We have recently improved the algorithm to incorporate exchange of certain bit-valued information between the agents over a directed communication graph. An interaction graph is introduced to encode known interactions. Restrictions on the payoff structure are eliminated and conditions that guarantee convergence to welfare minimizing actions w.p. 1 are derived under the assumption that the union of the interaction and communication graphs is strongly connected.