# American Institute of Mathematical Sciences

July  2014, 1(3): 447-469. doi: 10.3934/jdg.2014.1.447

## A primal condition for approachability with partial monitoring

 1 Faculty of Electrical Engineering, The Technion, 32 000 Haifa, Israel 2 LPMA, Université Paris-Diderot, 8 place FM/13, 75 013 Paris, France 3 GREGHEC, HEC Paris - CNRS, 1 rue de la Libération, 78 351 Jouy-en-Josas, France

Received  January 2013 Revised  March 2013 Published  July 2014

In approachability with full monitoring there are two types of conditions that are known to be equivalent for convex sets: a primal and a dual condition. The primal one is of the form: a set $\mathcal{C}$ is approachable if and only all containing half-spaces are approachable in the one-shot game. The dual condition is of the form: a convex set $\mathcal{C}$ is approachable if and only if it intersects all payoff sets of a certain form. We consider approachability in games with partial monitoring. In previous works [5，7] we provided a dual characterization of approachable convex sets and we also exhibited efficient strategies in the case where $\mathcal{C}$ is a polytope. In this paper we provide primal conditions on a convex set to be approachable with partial monitoring. They depend on a modified reward function and lead to approachability strategies based on modified payoff functions and that proceed by projections similarly to Blackwell's (1956) strategy. This is in contrast with previously studied strategies in this context that relied mostly on the signaling structure and aimed at estimating well the distributions of the signals received. Our results generalize classical results by Kohlberg [3] (see also [6]) and apply to games with arbitrary signaling structure as well as to arbitrary convex sets.
Citation: Shie Mannor, Vianney Perchet, Gilles Stoltz. A primal condition for approachability with partial monitoring. Journal of Dynamics and Games, 2014, 1 (3) : 447-469. doi: 10.3934/jdg.2014.1.447
##### References:
 [1] R. Aumann and M. Maschler, Repeated Games with Incomplete Information, MIT Press, 1995. [2] D. Blackwell, An analog of the minimax theorem for vector payoffs, Pacific Journal of Mathematics, 6 (1956), 1-8. doi: 10.2140/pjm.1956.6.1. [3] E. Kohlberg, Optimal strategies in repeated games with incomplete information, International Journal of Game Theory, 4 (1975), 7-24. doi: 10.1007/BF01766399. [4] G. Lugosi, S. Mannor and G. Stoltz, Strategies for prediction under imperfect monitoring, Mathematics of Operations Research, 33 (2008), 513-528. doi: 10.1287/moor.1080.0312. [5] S. Mannor, V. Perchet and G. Stoltz, Robust approachability and regret minimization in games with partial monitoring, http://hal.archives-ouvertes.fr/hal-00595695, 2012; An extended abstract was published in Proceedings of COLT'11. [6] J.-F. Mertens, S. Sorin and S. Zamir, Repeated Games, Technical Report no. 9420, 9421, 9422, Université de Louvain-la-Neuve, 1994. [7] V. Perchet, Approachability of convex sets in games with partial monitoring, Journal of Optimization Theory and Applications, 149 (2011), 665-677. doi: 10.1007/s10957-011-9797-3. [8] V. Perchet, Internal regret with partial monitoring: Calibration-based optimal algorithms, Journal of Machine Learning Research, 12 (2011), 1893-1921. [9] V. Perchet and M. Quincampoix, On an unified framework for approachability in games with or without signals, 2011., Available from: , (). [10] S. Sorin, A First Course on Zero-Sum Repeated Games, Mathématiques & Applications, no. 37, Springer, 2002.

show all references

##### References:
 [1] R. Aumann and M. Maschler, Repeated Games with Incomplete Information, MIT Press, 1995. [2] D. Blackwell, An analog of the minimax theorem for vector payoffs, Pacific Journal of Mathematics, 6 (1956), 1-8. doi: 10.2140/pjm.1956.6.1. [3] E. Kohlberg, Optimal strategies in repeated games with incomplete information, International Journal of Game Theory, 4 (1975), 7-24. doi: 10.1007/BF01766399. [4] G. Lugosi, S. Mannor and G. Stoltz, Strategies for prediction under imperfect monitoring, Mathematics of Operations Research, 33 (2008), 513-528. doi: 10.1287/moor.1080.0312. [5] S. Mannor, V. Perchet and G. Stoltz, Robust approachability and regret minimization in games with partial monitoring, http://hal.archives-ouvertes.fr/hal-00595695, 2012; An extended abstract was published in Proceedings of COLT'11. [6] J.-F. Mertens, S. Sorin and S. Zamir, Repeated Games, Technical Report no. 9420, 9421, 9422, Université de Louvain-la-Neuve, 1994. [7] V. Perchet, Approachability of convex sets in games with partial monitoring, Journal of Optimization Theory and Applications, 149 (2011), 665-677. doi: 10.1007/s10957-011-9797-3. [8] V. Perchet, Internal regret with partial monitoring: Calibration-based optimal algorithms, Journal of Machine Learning Research, 12 (2011), 1893-1921. [9] V. Perchet and M. Quincampoix, On an unified framework for approachability in games with or without signals, 2011., Available from: , (). [10] S. Sorin, A First Course on Zero-Sum Repeated Games, Mathématiques & Applications, no. 37, Springer, 2002.

Impact Factor: