{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T22:01:20Z","timestamp":1747173680078,"version":"3.40.5"},"reference-count":48,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T00:00:00Z","timestamp":1690761600000},"content-version":"unspecified","delay-in-days":30,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The tension between deduction and induction is perhaps the most fundamental issue in areas such as philosophy, cognition, and artificial intelligence. In an influential paper,<jats:italic>Valiant<\/jats:italic>recognized that the challenge of learning should be integrated with deduction. In particular, he proposed a semantics to capture the quality possessed by the output of<jats:italic>probably approximately correct<\/jats:italic>(PAC) learning algorithms when formulated in a logic. Although weaker than classical entailment, it allows for a powerful model-theoretic framework for answering queries. In this paper, we provide a new technical foundation to demonstrate PAC learning with multi-agent epistemic logics. To circumvent the negative results in the literature on the difficulty of robust learning with the PAC semantics, we consider so-called implicit learning where we are able to incorporate observations to the background theory in service of deciding the entailment of an epistemic query. We prove correctness of the learning procedure and discuss results on the sample complexity, that is how many observations we will need to provably assert that the query is entailed given a user-specified error bound. Finally, we investigate under what circumstances this algorithm can be made efficient. On the last point, given that reasoning in epistemic logics especially in multi-agent epistemic logics is PSPACE-complete, it might seem like there is no hope for this problem. We leverage some recent results on the so-called<jats:italic>Representation Theorem<\/jats:italic>explored for single-agent and multi-agent epistemic logics with the<jats:italic>only knowing<\/jats:italic>operator to reduce modal reasoning to propositional reasoning.<\/jats:p>","DOI":"10.1017\/s1471068423000182","type":"journal-article","created":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T11:40:01Z","timestamp":1690803601000},"page":"730-747","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Learnability with PAC Semantics for Multi-agent Beliefs"],"prefix":"10.1017","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6338-680X","authenticated-orcid":false,"given":"IONELA G.","family":"MOCANU","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5573-8465","authenticated-orcid":false,"given":"VAISHAK","family":"BELLE","sequence":"additional","affiliation":[]},{"given":"BRENDAN","family":"JUBA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,7,31]]},"reference":[{"key":"S1471068423000182_ref36","unstructured":"Liu, Y. and Levesque, H. 2005. Tractable reasoning with incomplete first-order knowledge in dynamic systems with context-dependent actions. In IJCAI, 522\u2013527."},{"key":"S1471068423000182_ref10","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897520"},{"key":"S1471068423000182_ref47","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00002-3"},{"key":"S1471068423000182_ref28","unstructured":"Kullmann, O. 1999. Investigating a general hierarchy of polynomially decidable classes of CNF\u2019s based on short tree-like resolution proofs. Tech. Rep. TR99-041, ECCC."},{"key":"S1471068423000182_ref7","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4192"},{"key":"S1471068423000182_ref39","unstructured":"Mocanu, I. , Belle, V. , and Juba, B. 2020. Polynomial-time implicit learnability in SMT. In ECAI 2020. Frontiers in Artificial Intelligence and Applications. IOS Press, Netherlands, 1152\u20131158."},{"key":"S1471068423000182_ref46","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"S1471068423000182_ref9","doi-asserted-by":"crossref","unstructured":"Bolander, T. and Gierasimczuk, N. 2015. Learning actions models: Qualitative approach. In Logic, Rationality, and Interaction, van der Hoek, W. , Holliday, W. H. , and Wang, W.-f. , Eds. LNCS, vol. 9394. Springer, 40\u201352.","DOI":"10.1007\/978-3-662-48561-3_4"},{"key":"S1471068423000182_ref4","doi-asserted-by":"crossref","unstructured":"Belardinelli, F. and Lomuscio, A. 2007. A quantified epistemic logic for reasoning about multiagent systems. In AAMAS, 1\u20133.","DOI":"10.1145\/1329125.1329231"},{"key":"S1471068423000182_ref33","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/4290.001.0001"},{"key":"S1471068423000182_ref40","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(94)90035-3"},{"key":"S1471068423000182_ref13","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.2921"},{"key":"S1471068423000182_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2018.01.002"},{"key":"S1471068423000182_ref22","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S1471068423000182_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/174652.174658"},{"key":"S1471068423000182_ref31","doi-asserted-by":"crossref","unstructured":"Lakemeyer, G. and Levesque, H. J. 2020. A first-order logic of limited belief based on possible worlds. In KR, 624\u2013635.","DOI":"10.24963\/kr.2020\/62"},{"key":"S1471068423000182_ref38","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v30i1.10110"},{"key":"S1471068423000182_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.03.004"},{"key":"S1471068423000182_ref5","unstructured":"Belle, V. 2010. Multi-agent only-knowing revisited. In AlgoSyn, 16."},{"key":"S1471068423000182_ref34","unstructured":"Liu, Y. , Lakemeyer, G. and Levesque, H. J. 2004. A logic of limited belief for reasoning with disjunctive information. In KR."},{"key":"S1471068423000182_ref25","doi-asserted-by":"crossref","unstructured":"Juba, B. 2015. Restricted distribution automatizability in PAC-semantics. In ITCS, 93\u2013102.","DOI":"10.1145\/2688073.2688108"},{"key":"S1471068423000182_ref19","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/7432.001.0001"},{"key":"S1471068423000182_ref45","unstructured":"Schwering, C. and Pagnucco, M. 2019. A representation theorem for reasoning in first-order multi-agent knowledge bases. In AAMAS. 926\u2013934."},{"key":"S1471068423000182_ref43","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(99)00083-1"},{"year":"2016","author":"Baltag","key":"S1471068423000182_ref3"},{"key":"S1471068423000182_ref20","doi-asserted-by":"publisher","DOI":"10.1111\/0824-7935.00036"},{"key":"S1471068423000182_ref24","first-page":"939","article-title":"Implicit learning of common sense for reasoning","author":"Juba","year":"2013","journal-title":"IJCAI"},{"key":"S1471068423000182_ref6","first-page":"3381","article-title":"Implicitly learning to reason in first-order logic","volume":"32","author":"Belle","year":"2019","journal-title":"Advances in Neural Information Processing Systems"},{"key":"S1471068423000182_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/0206031"},{"key":"S1471068423000182_ref30","unstructured":"Lakemeyer, G. and Levesque, H. J. 2004. Situations, Si! situation terms, No! In KR. 516\u2013526."},{"key":"S1471068423000182_ref17","unstructured":"Fan, J. , Wang, Y. , and van Ditmarsch, H. 2013. Knowing whether. CoRR abs\/1312.0144."},{"key":"S1471068423000182_ref23","unstructured":"Juba, B. 2012. Learning implicitly in reasoning in PAC-semantics. CoRR abs\/1209.0056."},{"key":"S1471068423000182_ref35","unstructured":"Liu, Y. and Levesque, H. 2003. A tractability result for reasoning with incomplete first-order knowledge bases. In IJCAI, 83\u201388."},{"key":"S1471068423000182_ref32","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90056-6"},{"key":"S1471068423000182_ref44","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00365-X"},{"key":"S1471068423000182_ref48","unstructured":"van Ditmarsch, H. , Halpern, J. Y. , van der Hoek, W. and Kooi, B. P. 2015. An introduction to logics of knowledge and belief. CoRR abs\/1503.00806."},{"key":"S1471068423000182_ref14","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.306.54"},{"key":"S1471068423000182_ref29","unstructured":"Lakemeyer, G. and Lesp\u00e9rance, Y. 2012. Efficient reasoning in multiagent epistemic logics. In ECAI."},{"key":"S1471068423000182_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265918"},{"year":"2003","author":"Halpern","key":"S1471068423000182_ref21"},{"key":"S1471068423000182_ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103605"},{"key":"S1471068423000182_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"S1471068423000182_ref42","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/195"},{"key":"S1471068423000182_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(99)00031-4"},{"key":"S1471068423000182_ref12","doi-asserted-by":"crossref","unstructured":"De Raedt, L. and Kersting, K. 2011. Statistical relational learning. In Encyclopedia of Machine Learning.","DOI":"10.1007\/978-0-387-30164-8_786"},{"key":"S1471068423000182_ref16","doi-asserted-by":"crossref","unstructured":"Fagin, R. , Halpern, J. Y. , Moses, Y. and Vardi, M. Y. 1995. Reasoning About Knowledge. MIT Press.","DOI":"10.7551\/mitpress\/5803.001.0001"},{"key":"S1471068423000182_ref8","unstructured":"Belle, V. and Lakemeyer, G. 2015. Only knowing meets common knowledge. In IJCAI."},{"key":"S1471068423000182_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/11595014_53"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068423000182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T10:51:36Z","timestamp":1729853496000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068423000182\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["S1471068423000182"],"URL":"https:\/\/doi.org\/10.1017\/s1471068423000182","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}