The IMP game: learnability, approximability and adversarial learning beyond ^0_1

DOI10.1093/LOGCOM/EXW031zbMATH Open1380.68241arXiv1602.02743OpenAlexW2963314587MaRDI QIDQ3133192FDOQ3133192

Authors: Michael Brand, David L. Dowe 

Publication date: 13 February 2018

Published in: Journal Of Logic And Computation (Search for Journal in Brave)

Abstract: We introduce a problem set-up we call the Iterated Matching Pennies (IMP) game and show that it is a powerful framework for the study of three problems: adversarial learnability, conventional (i.e., non-adversarial) learnability and approximability. Using it, we are able to derive the following theorems. (1) It is possible to learn by example all of $Sigm{a}_1^{0}cupP{i}_1^0$ as well as some supersets; (2) in adversarial learning (which we describe as a pursuit-evasion game), the pursuer has a winning strategy (in other words, $Sigm{a}_1^0$ can be learned adversarially, but $P{i}_1^0$ not); (3) some languages in $P{i}_1^0$ cannot be approximated by any language in $Sigm{a}_1^0$. We show corresponding results also for $Sigm{a}_i^0$ and $P{i}_i^0$ for arbitrary $i$.

Full work available at URL: https://arxiv.org/abs/1602.02743

Recommendations

• Inclusion problems in parallel learning and games
• Simple complexity from imitation games
• Characterizing PAC-learnability of semilinear sets
• Learning theory in the arithmetic hierarchy
• scientific article; zbMATH DE number 1104340

Mathematics Subject Classification ID

Computational learning theory (68Q32) Applications of game theory (91A80) Positional games (pursuit and evasion, etc.) (91A24) Rationality and learning in game theory (91A26) Recursive functions and relations, subrecursive hierarchies (03D20)

This page was built for publication: The IMP game: learnability, approximability and adversarial learning beyond \(\Sigma^0_1\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133192)