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

DOI10.1093/LOGCOM/EXW031MaRDI QIDQ3133192zbMATH OpenOpenAlexFDO

Publication date 13 February 2018

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

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

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)

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

S i g m a_{1}^{0} c u p P 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,

S i g m 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

S i g m a_{1}^{0}

. We show corresponding results also for

S i g m a_{i}^{0}

and

P i_{i}^{0}

for arbitrary

i

.

Recommendations

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)