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 & 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).   Google Scholar

[2]

D. Blackwell, An analog of the minimax theorem for vector payoffs,, Pacific Journal of Mathematics, 6 (1956), 1.  doi: 10.2140/pjm.1956.6.1.  Google Scholar

[3]

E. Kohlberg, Optimal strategies in repeated games with incomplete information,, International Journal of Game Theory, 4 (1975), 7.  doi: 10.1007/BF01766399.  Google Scholar

[4]

G. Lugosi, S. Mannor and G. Stoltz, Strategies for prediction under imperfect monitoring,, Mathematics of Operations Research, 33 (2008), 513.  doi: 10.1287/moor.1080.0312.  Google Scholar

[5]

S. Mannor, V. Perchet and G. Stoltz, Robust approachability and regret minimization in games with partial monitoring,, , (2012).   Google Scholar

[6]

J.-F. Mertens, S. Sorin and S. Zamir, Repeated Games,, Technical Report no. 9420, (9420).   Google Scholar

[7]

V. Perchet, Approachability of convex sets in games with partial monitoring,, Journal of Optimization Theory and Applications, 149 (2011), 665.  doi: 10.1007/s10957-011-9797-3.  Google Scholar

[8]

V. Perchet, Internal regret with partial monitoring: Calibration-based optimal algorithms,, Journal of Machine Learning Research, 12 (2011), 1893.   Google Scholar

[9]

V. Perchet and M. Quincampoix, On an unified framework for approachability in games with or without signals, 2011., Available from: , ().   Google Scholar

[10]

S. Sorin, A First Course on Zero-Sum Repeated Games,, Mathématiques & Applications, (2002).   Google Scholar

show all references

References:
[1]

R. Aumann and M. Maschler, Repeated Games with Incomplete Information,, MIT Press, (1995).   Google Scholar

[2]

D. Blackwell, An analog of the minimax theorem for vector payoffs,, Pacific Journal of Mathematics, 6 (1956), 1.  doi: 10.2140/pjm.1956.6.1.  Google Scholar

[3]

E. Kohlberg, Optimal strategies in repeated games with incomplete information,, International Journal of Game Theory, 4 (1975), 7.  doi: 10.1007/BF01766399.  Google Scholar

[4]

G. Lugosi, S. Mannor and G. Stoltz, Strategies for prediction under imperfect monitoring,, Mathematics of Operations Research, 33 (2008), 513.  doi: 10.1287/moor.1080.0312.  Google Scholar

[5]

S. Mannor, V. Perchet and G. Stoltz, Robust approachability and regret minimization in games with partial monitoring,, , (2012).   Google Scholar

[6]

J.-F. Mertens, S. Sorin and S. Zamir, Repeated Games,, Technical Report no. 9420, (9420).   Google Scholar

[7]

V. Perchet, Approachability of convex sets in games with partial monitoring,, Journal of Optimization Theory and Applications, 149 (2011), 665.  doi: 10.1007/s10957-011-9797-3.  Google Scholar

[8]

V. Perchet, Internal regret with partial monitoring: Calibration-based optimal algorithms,, Journal of Machine Learning Research, 12 (2011), 1893.   Google Scholar

[9]

V. Perchet and M. Quincampoix, On an unified framework for approachability in games with or without signals, 2011., Available from: , ().   Google Scholar

[10]

S. Sorin, A First Course on Zero-Sum Repeated Games,, Mathématiques & Applications, (2002).   Google Scholar

[1]

Andy Hammerlindl, Jana Rodriguez Hertz, Raúl Ures. Ergodicity and partial hyperbolicity on Seifert manifolds. Journal of Modern Dynamics, 2020, 0: 331-348. doi: 10.3934/jmd.2020012

[2]

Nicholas Geneva, Nicholas Zabaras. Multi-fidelity generative deep learning turbulent flows. Foundations of Data Science, 2020, 2 (4) : 391-428. doi: 10.3934/fods.2020019

[3]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[4]

Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073

[5]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264

[6]

Tien-Yu Lin, Bhaba R. Sarker, Chien-Jui Lin. An optimal setup cost reduction and lot size for economic production quantity model with imperfect quality and quantity discounts. Journal of Industrial & Management Optimization, 2021, 17 (1) : 467-484. doi: 10.3934/jimo.2020043

[7]

Yen-Luan Chen, Chin-Chih Chang, Zhe George Zhang, Xiaofeng Chen. Optimal preventive "maintenance-first or -last" policies with generalized imperfect maintenance models. Journal of Industrial & Management Optimization, 2021, 17 (1) : 501-516. doi: 10.3934/jimo.2020149

[8]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[9]

Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054

[10]

Kengo Nakai, Yoshitaka Saiki. Machine-learning construction of a model for a macroscopic fluid variable using the delay-coordinate of a scalar observable. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1079-1092. doi: 10.3934/dcdss.2020352

[11]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[12]

Yantao Wang, Linlin Su. Monotone and nonmonotone clines with partial panmixia across a geographical barrier. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 4019-4037. doi: 10.3934/dcds.2020056

[13]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458

[14]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024

[15]

Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310

[16]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051

[17]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025

[18]

Musen Xue, Guowei Zhu. Partial myopia vs. forward-looking behaviors in a dynamic pricing and replenishment model for perishable items. Journal of Industrial & Management Optimization, 2021, 17 (2) : 633-648. doi: 10.3934/jimo.2019126

[19]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

[20]

Jann-Long Chern, Sze-Guang Yang, Zhi-You Chen, Chih-Her Chen. On the family of non-topological solutions for the elliptic system arising from a product Abelian gauge field theory. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127

 Impact Factor: 

Metrics

  • PDF downloads (30)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]