* Klakow (2000) Dietrich Klakow. 2000.  Selecting articles from the language model training corpus.  In _2000 IEEE International Conference on Acoustics, Speech, and Signal Processing_ , pages 1695–1698, Istanbul, Turkey.
  * Klementiev and Roth (2006) Alexandre Klementiev and Dan Roth. 2006.  Weakly supervised named entity transliteration and discovery from multilingual comparable corpora.  In _Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics_ , pages 817–824, Sydney, Australia.
  * Kobayashi (2018) Sosuke Kobayashi. 2018.  Contextual augmentation: Data augmentation by words with paradigmatic relations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 452–457, New Orleans, Louisiana.
  * Kohane et al. (2006) Isaac S Kohane, Daniel R Masys, and Russ B Altman. 2006.  The incidentalome: a threat to genomic medicine.  _The Journal of the American Medical Association_ , pages 212–215.
  * Kulkarni et al. (2018) Chaitanya Kulkarni, Wei Xu, Alan Ritter, and Raghu Machiraju. 2018.  An annotated corpus for machine reading of instructions in wet lab protocols.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 97–106, New Orleans, Louisiana.
  * Laclavík et al. (2012) Michal Laclavík, Štefan Dlugolinský, Martin Šeleng, Marcel Kvassay, Emil Gatial, Zoltán Balogh, and Ladislav Hluchý. 2012.  Email analysis and information extraction for enterprise benefit.  _Computing and informatics_ , pages 57–87.
  * Lample et al. (2016) Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016.  Neural architectures for named entity recognition.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 260–270, San Diego, California.
  * Lange et al. (2020) Lukas Lange, Xiang Dai, Heike Adel, and Jannik Strötgen. 2020.  NLNDE at CANTEMIST: Neural sequence labeling and parsing approaches for clinical concept extraction.  In _Iberian Languages Evaluation Forum (IberLEF 2020)_ , pages 335–346, Online.
  * Lange et al. (2019) Lukas Lange, Michael A Hedderich, and Dietrich Klakow. 2019.  Feature-dependent confusion matrices for low-resource ner labeling with noisy labels.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3554–3559, Hong Kong, China.
  * Leaman et al. (2015) Robert Leaman, Ritu Khare, and Zhiyong Lu. 2015.  Challenges in clinical natural language processing for automated disorder normalization.  _Journal of biomedical informatics_ , pages 28–37.
  * Leaman et al. (2010) Robert Leaman, Laura Wojtulewicz, Ryan Sullivan, Annie Skariah, Jian Yang, and Graciela Gonzalez. 2010.  Towards internet-age pharmacovigilance: extracting adverse drug reactions from user posts in health-related social networks.  In _Proceedings of the 2010 workshop on biomedical natural language processing_ , pages 117–125, Uppsala, Sweden.
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. 2015.  Deep learning.  _Nature_ , pages 436–444.
  * Lee (2001) David YW Lee. 2001.  Genres, registers, text types, domains and styles: Clarifying the concepts and nevigating a path through the bnc jungle.  _Language Learning and Technology_ , pages 37–72.
  * Lee et al. (2020) Jinhyuk Lee, Wonjin Yoon, Sungdong Kim, Donghyeon Kim, Sunkyu Kim, Chan Ho So, and Jaewoo Kang. 2020.  BioBERT: a pre-trained biomedical language representation model for biomedical text mining.  _Bioinformatics_ , pages 1234–1240.
  * Li et al. (2020) Jing Li, Aixin Sun, Jianglei Han, and Chenliang Li. 2020.  A survey on deep learning for named entity recognition.  _IEEE Transactions on Knowledge and Data Engineering_.
  * Li et al. (2017) Peng-Hsuan Li, Ruo-Ping Dong, Yu-Siang Wang, Ju-Chieh Chou, and Wei-Yun Ma. 2017\.  Leveraging linguistic structures for named entity recognition with bidirectional recursive neural networks.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2664–2669, Copenhagen, Denmark.
  * Liang et al. (2020) Chen Liang, Yue Yu, Haoming Jiang, Siawpeng Er, Ruijia Wang, Tuo Zhao, and Chao Zhang. 2020.  Bond: Bert-assisted open-domain named entity recognition with distant supervision.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , page 1054–1064, Online.
  * Lin et al. (2019) Hongyu Lin, Yaojie Lu, Xianpei Han, and Le Sun. 2019.  Sequence-to-nuggets: Nested entity mention detection via anchor-region networks.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5182–5192, Florence, Italy.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Lu and Roth (2015) Wei Lu and Dan Roth. 2015.  Joint mention extraction and classification with mention hypergraphs.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 857–867, Lisbon, Portugal.
  * Luan et al. (2018) Yi Luan, Luheng He, Mari Ostendorf, and Hannaneh Hajishirzi. 2018.  Multi-task identification of entities, relations, and coreference for scientific knowledge graph construction.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3219–3232, Brussels, Belgium.
  * Luan et al. (2019) Yi Luan, Dave Wadden, Luheng He, Amy Shah, Mari Ostendorf, and Hannaneh Hajishirzi. 2019.  A general framework for information extraction using dynamic span graphs.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 3036–3046, Minneapolis, Minnesota.
  * Luong et al. (2015) Minh-Thang Luong, Hieu Pham, and Christopher D Manning. 2015.  Effective approaches to attention-based neural machine translation.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 1412–1421, Lisbon, Portugal.
  * Ma and Hovy (2016) Xuezhe Ma and Eduard Hovy. 2016.  End-to-end sequence labeling via bi-directional LSTM-CNNs-CRF.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1064–1074, Berlin, Germany.
  * McDonald et al. (2005) Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005.  Flexible text segmentation with structured multilabel classification.  In _Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing_ , pages 987–994, Vancouver, Canada.
  * Merity et al. (2016) Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. 2016.  Pointer sentinel mixture models.  _arXiv preprint arXiv:1609.07843_.
  * Mesbah et al. (2019) Sepideh Mesbah, Jie Yang, Robert-Jan Sips, Manuel Valle Torre, Christoph Lofi, Alessandro Bozzon, and Geert-Jan Houben. 2019.  Training data augmentation for detecting adverse drug reactions in user-generated content.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 2349–2359, Hong Kong, China.
  * Metke-Jimenez and Karimi (2016) Alejandro Metke-Jimenez and Sarvnaz Karimi. 2016.  Concept identification and normalisation for adverse drug event discovery in medical forums.  In _Proceedings of the First International Workshop on Biomedical Data Integration and Discovery_ , Kobe, Japan.
  * Mikheev et al. (1999) Andrei Mikheev, Marc Moens, and Claire Grover. 1999.  Named entity recognition without gazetteers.  In _Ninth Conference of the European Chapter of the Association for Computational Linguistics_ , pages 1–8, Bergen, Norway.
  * Mikolov et al. (2013a) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013a.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_.
  * Mikolov et al. (2018) Tomas Mikolov, Edouard Grave, Piotr Bojanowski, Christian Puhrsch, and Armand Joulin. 2018.  Advances in pre-training distributed word representations.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , pages 52–55, Miyazaki, Japan.
  * Mikolov et al. (2013b) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013b.  Distributed representations of words and phrases and their compositionality.  In _27th Annual Conference on Neural Information Processing Systems_ , pages 3111–3119, Lake Tahoe, Nevada.
  * Miller et al. (1990) George A Miller, Richard Beckwith, Christiane Fellbaum, Derek Gross, and Katherine J Miller. 1990.  Introduction to WordNet: An on-line lexical database.  _International journal of lexicography_ , pages 235–244.
  * Min et al. (2020) Junghyun Min, R Thomas McCoy, Dipanjan Das, Emily Pitler, and Tal Linzen. 2020.  Syntactic data augmentation increases robustness to inference heuristics.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2339–2352, Online.
  * Moore and Lewis (2010) Robert C Moore and Will Lewis. 2010.  Intelligent selection of language model training data.  In _Proceedings of the ACL 2010 Conference Short Papers_ , pages 220–224, Uppsala, Sweden.
  * Mouton et al. (2015) Johannes P Mouton, Ushma Mehta, Andy G Parrish, Douglas PK Wilson, Annemie Stewart, Christine W Njuguna, Nicole Kramer, Gary Maartens, Marc Blockman, and Karen Cohen. 2015.  Mortality from adverse drug reactions in adult medical inpatients at four hospitals in south africa: a cross-sectional survey.  _British journal of clinical pharmacology_ , pages 818–826.
  * Mowery et al. (2014) Danielle L Mowery, Sumithra Velupillai, Brett R South, Lee Christensen, David Martinez, Liadh Kelly, Lorraine Goeuriot, Noemie Elhadad, Sameer Pradhan, and Guergana Savova. 2014.  Task 2: ShARe/CLEF ehealth evaluation lab 2014.  In _Conference and Labs of the Evaluation Forum_ , pages 31–42, Sheffield, United Kingdom.
  * Muis and Lu (2016) Aldrian Obaja Muis and Wei Lu. 2016.  Learning to recognize discontiguous entities.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 75–84, Austin, Texas.
  * Muis and Lu (2017) Aldrian Obaja Muis and Wei Lu. 2017.  Labeling gaps between words: Recognizing overlapping mentions with mention separators.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2608–2618, Copenhagen, Denmark.
  * n2c2 (2019) n2c2. 2019.  Track 2: n2c2/OHNLP track on family history extraction.  Web page, Harvard Medical School – Department of Biomedical Informatics.
  * Nadeau and Sekine (2007) David Nadeau and Satoshi Sekine. 2007.  A survey of named entity recognition and classification.  _Lingvisticae Investigationes_ , pages 3–26.
  * Nguyen et al. (2020) Dat Quoc Nguyen, Thanh Vu, and Anh Tuan Nguyen. 2020.  BERTweet: A pre-trained language model for English tweets.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 9–14, Online.
  * Nothman et al. (2008) Joel Nothman, James R Curran, and Tara Murphy. 2008.  Transforming wikipedia into named entity training data.  In _Proceedings of the Australasian Language Technology Association Workshop 2008_ , pages 124–132, Hobart, Australia.
  * Nye et al. (2018) Benjamin Nye, Junyi Jessy Li, Roma Patel, Yinfei Yang, Iain J Marshall, Ani Nenkova, and Byron C Wallace. 2018.  A corpus with multi-level annotations of patients, interventions and outcomes to support language processing for medical literature.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 197–207, Melbourne, Australia.
  * Olsson (2009) Fredrik Olsson. 2009.  A literature survey of active machine learning in the context of natural language processing.  Technical report, Swedish Institute of Computer Science.
  * Pan and Yang (2009) Sinno Jialin Pan and Qiang Yang. 2009.  A survey on transfer learning.  _IEEE Transactions on Knowledge and Data Engineering_ , pages 1345–1359.
  * Patra and Moniz (2019) Barun Patra and Joel Ruben Antony Moniz. 2019.  Weakly supervised attention networks for entity recognition.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 6269–6274, Hong Kong, China.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014.  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543, Doha, Qatar.
  * Peters et al. (2017) Matthew E Peters, Waleed Ammar, Chandra Bhagavatula, and Russell Power. 2017.  Semi-supervised sequence tagging with bidirectional language models.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1756–1765, Vancouver, Canada.
  * Peters et al. (2018) Matthew E Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep contextualized word representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 2227–2237, New Orleans, Louisiana.
  * Petrov et al. (2006) Slav Petrov, Leon Barrett, Romain Thibaux, and Dan Klein. 2006.  Learning accurate, compact, and interpretable tree annotation.  In _Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics_ , pages 433–440, Sydney, Australia.
  * Piazza-Hepp and Kennedy (1995) Toni D. Piazza-Hepp and Dianne L. Kennedy. 1995.  Reporting of adverse events to medwatch.  _American Journal of Health-System Pharmacy_ , pages 1436–1439.
  * Plank and van Noord (2011) Barbara Plank and Gertjan van Noord. 2011.  Effective measures of domain similarity for parsing.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 1566–1576, Portland, Oregon, USA.
  * Pradhan et al. (2013) Sameer Pradhan, Noemie Elhadad, Brett R South, David Martinez, Lee M Christensen, Amy Vogel, Hanna Suominen, Wendy W Chapman, and Guergana K Savova. 2013.  Task 1: ShARe/CLEF ehealth evaluation lab 2013.  In _Conference and Labs of the Evaluation Forum_ , pages 212–31, Valencia, Spain.
  * Rahimi et al. (2019) Afshin Rahimi, Yuan Li, and Trevor Cohn. 2019.  Massively multilingual transfer for ner.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 151–164, Florence, Italy.
  * Raiman and Miller (2017) Jonathan Raiman and John Miller. 2017.  Globally normalized reader.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1059–1069, Copenhagen, Denmark.
  * Ramponi and Plank (2020) Alan Ramponi and Barbara Plank. 2020.  Neural unsupervised domain adaptation in NLP—A survey.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 6838–6855, Barcelona, Spain (Online).
  * Ringland et al. (2019) Nicky Ringland, Xiang Dai, Ben Hachey, Sarvnaz Karimi, Cecile Paris, and James R Curran. 2019.  NNE: A dataset for nested named entity recognition in English newswire.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5176–5181, Florence, Italy.
  * Ringland (2016) Nicola Ringland. 2016.  _Structured Named Entities_.  Thesis, University of Sydney.
  * Rohanian et al. (2019) Omid Rohanian, Shiva Taslimipoor, Samaneh Kouchaki, Le An Ha, and Ruslan Mitkov. 2019.  Bridging the gap: Attending to discontinuity in identification of multiword expressions.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 2692–2698, Minneapolis, Minnesota.
  * Ruder (2019) Sebastian Ruder. 2019.  _Neural transfer learning for natural language processing_.  Thesis, National University of Ireland Galway.
  * Ruder et al. (2019a) Sebastian Ruder, Joachim Bingel, Isabelle Augenstein, and Anders Søgaard. 2019a.  Latent multi-task architecture learning.  In _The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)_ , pages 4822–4829, Honolulu, Hawaii.
  * Ruder and Plank (2017) Sebastian Ruder and Barbara Plank. 2017.  Learning to select data for transfer learning with bayesian optimization.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 372–382, Copenhagen, Denmark.
  * Ruder et al. (2019b) Sebastian Ruder, Ivan Vulić, and Anders Søgaard. 2019b.  A survey of cross-lingual word embedding models.  _Journal of Artificial Intelligence Research_ , pages 569–631.
  * Rybinski et al. (2021) Maciej Rybinski, Xiang Dai, Sonit Singh, Sarvnaz Karimi, Anthony Nguyen, et al. 2021\.  Extracting family history information from electronic health records: Natural language processing analysis.  _JMIR Medical Informatics_ , 9(4):e24020.
  * Safranchik et al. (2020) Esteban Safranchik, Shiying Luo, and Stephen H Bach. 2020.  Weakly supervised sequence tagging from noisy rules.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20)_ , pages 5570–5578, New York, NY.
  * Şahin and Steedman (2019) Gözde Gül Şahin and Mark Steedman. 2019.  Data augmentation via dependency tree morphing for low-resource languages.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 5004–5009, Brussels, Belgium.
  * Sang (2002) Erik F. Tjong Kim Sang. 2002.  Introduction to the CoNLL-2002 shared task: Language-independent named entity recognition.  In _COLING-02: The 6th Conference on Natural Language Learning 2002 (CoNLL-2002)_ , Stroudsburg, PA.
  * Sang and Meulder (2003) Erik F. Tjong Kim Sang and Fien De Meulder. 2003.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  In _Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003_ , pages 142–147, Edmonton, Canada.
  * Sarawagi (2008) Sunita Sarawagi. 2008.  _Information extraction_.  Now Publishers Inc.
  * Sarker et al. (2015) Abeed Sarker, Rachel Ginn, Azadeh Nikfarjam, Karen O’Connor, Karen Smith, Swetha Jayaraman, Tejaswi Upadhaya, and Graciela Gonzalez. 2015.  Utilizing social media data for pharmacovigilance: a review.  _Journal of biomedical informatics_ , pages 202–212.
  * Scheffer et al. (2001) Tobias Scheffer, Christian Decomain, and Stefan Wrobel. 2001.  Active hidden markov models for information extraction.  In _International Symposium on Intelligent Data Analysis_ , pages 309–318, Cascais, Portugal.
  * Schwartz et al. (2019) Roy Schwartz, Jesse Dodge, Noah A Smith, and Oren Etzioni. 2019.  Green AI.  _arXiv preprint arXiv:1907.10597_.
  * Schütze et al. (2008) Hinrich Schütze, Christopher D Manning, and Prabhakar Raghavan. 2008.  _Introduction to information retrieval_.  Cambridge University Press Cambridge.
  * Sennrich et al. (2015) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2015.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany.
  * Settles (2009) Burr Settles. 2009.  Active learning literature survey.  Technical report, University of Wisconsin-Madison.
  * Settles and Craven (2008) Burr Settles and Mark Craven. 2008.  An analysis of active learning strategies for sequence labeling tasks.  In _Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing_ , pages 1070–1079, Honolulu, Hawaii.
  * Shen et al. (2014) Wei Shen, Jianyong Wang, and Jiawei Han. 2014.  Entity linking with a knowledge base: Issues, techniques, and solutions.  _IEEE Transactions on Knowledge and Data Engineering_ , pages 443–460.
  * Shen et al. (2018) Yanyao Shen, Hyokun Yun, Zachary C Lipton, Yakov Kronrod, and Animashree Anandkumar. 2018.  Deep active learning for named entity recognition.  In _International Conference on Learning Representations_ , Vancouver, Canada.
  * Shorten and Khoshgoftaar (2019) Connor Shorten and Taghi M Khoshgoftaar. 2019.  A survey on image data augmentation for deep learning.  _Journal of Big Data_ , page 60.
  * Smith et al. (2008) Larry Smith, Lorraine K Tanabe, Rie Johnson nee Ando, Cheng-Ju Kuo, I-Fang Chung, Chun-Nan Hsu, Yu-Shi Lin, Roman Klinger, Christoph M Friedrich, and Kuzman Ganchev. 2008.  Overview of biocreative ii gene mention recognition.  _Genome biology_ , page S2.
  * Sohrab and Miwa (2018) Mohammad Golam Sohrab and Makoto Miwa. 2018.  Deep exhaustive model for nested named entity recognition.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2843–2849, Brussels, Belgium.
  * Solano-Flores (2006) Guillermo Solano-Flores. 2006.  Language, dialect, and register: Sociolinguistics and the estimation of measurement error in the testing of english language learners.  _Teachers College Record_ , page 2354.
  * Stanovsky et al. (2017) Gabriel Stanovsky, Daniel Gruhl, and Pablo Mendes. 2017.  Recognizing mentions of adverse drug reaction in social media using knowledge-infused recurrent models.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers_ , pages 142–151, Valencia, Spain.
  * Stenetorp et al. (2012) Pontus Stenetorp, Sampo Pyysalo, Goran Topić, Tomoko Ohta, Sophia Ananiadou, and Jun’ichi Tsujii. 2012.  brat: a web-based tool for NLP-assisted text annotation.  In _Proceedings of the Demonstrations at the 13th Conference of the European Chapter of the Association for Computational Linguistics_ , pages 102–107, Avignon, France.
  * Strauss et al. (2016) Benjamin Strauss, Bethany Toma, Alan Ritter, Marie-Catherine De Marneffe, and Wei Xu. 2016.  Results of the wnut16 named entity recognition shared task.  In _Proceedings of the 2nd Workshop on Noisy User-generated Text_ , pages 138–144, Osaka, Japan.
  * Sun et al. (2019) Lin Sun, Fule Ji, Kai Zhang, and Chi Wang. 2019.  Multilayer toi detection approach for nested ner.  _IEEE Access_ , pages 186600–186608.
  * Sutton and McCallum (2007) Charles Sutton and Andrew McCallum. 2007.  _An introduction to conditional random fields for relational learning_.  The MIT Press.
  * Søgaard and Goldberg (2016) Anders Søgaard and Yoav Goldberg. 2016.  Deep multi-task learning with low level tasks supervised at lower layers.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 231–235, Berlin, Germany.
  * Tang et al. (2013a) Buzhou Tang, Hongxin Cao, Yonghui Wu, Min Jiang, and Hua Xu. 2013a.  Recognizing clinical entities in hospital discharge summaries using structural support vector machines with word representation features.  _BMC medical informatics and decision making_ , page S1.
  * Tang et al. (2018) Buzhou Tang, Jianglu Hu, Xiaolong Wang, and Qingcai Chen. 2018.  Recognizing continuous and discontinuous adverse drug reaction mentions from social media using lstm-crf.  _Wireless Communications and Mobile Computing_.
  * Tang et al. (2013b) Buzhou Tang, Yonghui Wu, Min Jiang, Joshua C Denny, and Hua Xu. 2013b.  Recognizing and encoding discorder concepts in clinical text using machine learning and vector space model.  In _Conference and Labs of the Evaluation Forum_ , Valencia, Spain.
  * Tkachenko et al. (2013) Alexander Tkachenko, Timo Petmanson, and Sven Laur. 2013.  Named entity recognition in Estonian.  In _Proceedings of the 4th Biennial International Workshop on Balto-Slavic Natural Language Processing_ , pages 78–83, Sofia, Bulgaria.
  * Uzuner et al. (2011) Özlem Uzuner, Brett R South, Shuying Shen, and Scott L DuVall. 2011.  2010 i2b2/VA challenge on concepts, assertions, and relations in clinical text.  _Journal of the American Medical Informatics Association_ , pages 552–556.
  * Vallano et al. (2005) A Vallano, G Cereza, C Pedròs, A Agustí, I Danés, C Aguilera, and JM Arnau. 2005\.  Obstacles and solutions for spontaneous reporting of adverse drug reactions in the hospital.  _British journal of clinical pharmacology_ , pages 653–658.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008, Long Beach, California.
  * Wang et al. (2019) Alex Wang, Jan Hula, Patrick Xia, Raghavendra Pappagari, R. Thomas McCoy, Roma Patel, Najoung Kim, Ian Tenney, Yinghui Huang, Katherin Yu, Shuning Jin, Berlin Chen, Benjamin Van Durme, Edouard Grave, Ellie Pavlick, and Samuel R. Bowman. 2019.  Can you tell me how to get past sesame street? sentence-level pretraining beyond language modeling.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4465–4476, Florence, Italy.
  * Wang and Lu (2018) Bailin Wang and Wei Lu. 2018.  Neural segmental hypergraphs for overlapping mention recognition.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 204–214, Brussels, Belgium.
  * Wang and Lu (2019) Bailin Wang and Wei Lu. 2019.  Combining spans into entities: A neural two-stage approach for recognizing discontiguous entities.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 6216–6224, Hong Kong, China.
  * Wang and Yang (2015) William Yang Wang and Diyi Yang. 2015.  That’s so annoying!!!: A lexical and frame-semantic embedding based data augmentation approach to automatic categorization of annoying behaviors using #petpeeve tweets.  In _Proceedings of the 2015 conference on empirical methods in natural language processing_ , pages 2557–2563, Lisbon, Portugal.
  * Wang et al. (2018a) Xinyi Wang, Hieu Pham, Zihang Dai, and Graham Neubig. 2018a.  SwitchOut: an efficient data augmentation algorithm for neural machine translation.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 856–861, Brussels, Belgium.
  * Wang et al. (2018b) Yanshan Wang, Liwei Wang, Majid Rastegar-Mojarad, Sungrim Moon, Feichen Shen, Naveed Afzal, Sijia Liu, Yuqun Zeng, Saeed Mehrabi, and Sunghwan Sohn. 2018b.  Clinical information extraction applications: a literature review.  _Journal of biomedical informatics_ , pages 34–49.
  * Watanabe and Sumita (2015) Taro Watanabe and Eiichiro Sumita. 2015.  Transition-based neural constituent parsing.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1169–1179, Beijing, China.
  * Wei and Zou (2019) Jason Wei and Kai Zou. 2019.  EDA: Easy data augmentation techniques for boosting performance on text classification tasks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 6382–6388, Hong Kong, China.
  * Weischedel et al. (2011) Ralph Weischedel, Eduard Hovy, Mitchell Marcus, Martha Palmer, Robert Belvin, Sameer Pradhan, Lance Ramshaw, and Nianwen Xue. 2011.  _OntoNotes: A large training corpus for enhanced processing_.  Springer.
  * Weiss et al. (2016) Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang. 2016.  A survey of transfer learning.  _Journal of Big data_ , page 9.
  * WHO (2020) WHO. 2020.  Safety of medicines – adverse drug reactions.  Web page, World Health Organization.
  * Xia et al. (2019a) Congying Xia, Chenwei Zhang, Tao Yang, Yaliang Li, Nan Du, Xian Wu, Wei Fan, Fenglong Ma, and Philip Yu. 2019a.  Multi-grained named entity recognition.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1430–1440, Florence, Italy.
  * Xia et al. (2019b) Mengzhou Xia, Xiang Kong, Antonios Anastasopoulos, and Graham Neubig. 2019b.  Generalized data augmentation for low-resource translation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 5786–5796, Florence, Italy.
  * Xie et al. (2019) Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V Le. 2019.  Unsupervised data augmentation for consistency training.  _arXiv preprint arXiv:1904.12848_.
  * Xu et al. (2017) Mingbin Xu, Hui Jiang, and Sedtawut Watcharawittayakul. 2017.  A local detection approach for named entity recognition and mention detection.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1237–1247, Vancouver, Canada.
  * Yadav and Bethard (2019) Vikas Yadav and Steven Bethard. 2019.  A survey on recent advances in named entity recognition from deep learning models.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 2145–2158, Santa Fe, New Mexico.
  * Yang et al. (2018) Jie Yang, Shuailong Liang, and Yue Zhang. 2018.  Design challenges and misconceptions in neural sequence labeling.  In _Proceedings of the 27th International Conference on Computational Linguistics_ , pages 3879–3889, Santa Fe, New Mexico.
  * Yang et al. (2017) Zhilin Yang, Ruslan Salakhutdinov, and William W Cohen. 2017.  Transfer learning for sequence tagging with hierarchical recurrent networks.  In _International Conference on Learning Representations (ICLR 2017)_ , Toulon, France.
  * Yoo et al. (2019) Kang Min Yoo, Youhyun Shin, and Sang goo Lee. 2019.  Data augmentation for spoken language understanding via joint variational generation.  In _The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)_ , pages 7402–7409, Honolulu, Hawaii.
  * Yu et al. (2018) Adams Wei Yu, David Dohan, Minh-Thang Luong, Rui Zhao, Kai Chen, Mohammad Norouzi, and Quoc V Le. 2018.  Qanet: Combining local convolution with global self-attention for reading comprehension.  In _International Conference on Learning Representations_ , Vancouver, Canada.
  * Yu et al. (2020) Juntao Yu, Bernd Bohnet, and Massimo Poesio. 2020.  Named entity recognition as dependency parsing.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 6470–6476, Online.
  * Zhang and Elhadad (2013) Shaodian Zhang and Noémie Elhadad. 2013.  Unsupervised biomedical named entity recognition: Experiments with clinical and biological texts.  _Journal of biomedical informatics_ , pages 1088–1098.
  * Zhang et al. (2015a) Shiliang Zhang, Hui Jiang, Mingbin Xu, Junfeng Hou, and Li-Rong Dai. 2015a.  The fixed-size ordinally-forgetting encoding method for neural network language models.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 495–500, Beijing, China.
  * Zhang et al. (2015b) Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015b.  Character-level convolutional networks for text classification.  In _Advances in neural information processing systems_ , pages 649–657, Montreal, Canada.
  * Zhao et al. (2018) Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. 2018\.  Gender bias in coreference resolution: Evaluation and debiasing methods.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 15–20, New Orleans, Louisiana.
  * Zheng et al. (2019) Changmeng Zheng, Yi Cai, Jingyun Xu, Ho fung Leung, and Guandong Xu. 2019.  A boundary-aware neural model for nested named entity recognition.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 357–366, Hong Kong, China.
  * Zhu et al. (2015) Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. 2015.  Aligning books and movies: Towards story-like visual explanations by watching movies and reading books.  In _Proceedings of the IEEE international conference on computer vision_ , pages 19–27, Santiago, Chile.


($\bar{F}\perp(Z,O,A)\setminus\bar{S}^{\prime}\mid\bar{S}^{\prime}$ )
$\displaystyle=\mathbb{E}_{(\bar{s})\sim
d^{\pi^{e}}_{t}}[\mathbb{E}[\mu(Z,O,A)b^{[t+1]}_{V}(\bar{F})\mid\bar{S}=\bar{s}]].$
(Total law of expectation)

Therefore,

$\displaystyle
J(\pi^{e})-\mathbb{E}_{\bar{f}\sim\nu_{\bar{\mathcal{F}}}}[b^{[0]}_{V}(\bar{f})]$
$\displaystyle=\left(\sum_{t=0}^{T-1}\mathbb{E}_{\bar{s}\sim
d^{\pi^{e}}_{t}}[\gamma^{t}\mathbb{E}[\mu(Z,O,A)R\mid\bar{S}=\bar{s}]\right)+\left(\sum_{t=0}^{T-1}\gamma^{t}\mathbb{E}_{(\bar{s})\sim
d^{\pi^{e}}_{t}}[\mathbb{E}[\gamma\mu(Z,O,A)b^{[t+1]}_{V}(\bar{F}^{\prime})-b^{[t]}_{V}(\bar{F})\mid\bar{S}=\bar{s}]]\right)$
$\displaystyle=\sum_{t=0}^{T-1}\gamma^{t}\mathbb{E}_{(\bar{s})\sim
d^{\pi^{e}}_{t}}[\mathbb{E}[\mu(Z,O,A)\\{R+\gamma
b^{[t+1]}_{V}(\bar{F}^{\prime})\\}-b^{[t]}_{V}(\bar{F})\mid\bar{S}=\bar{s}]]$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{E}_{(\bar{s})\sim
d^{\pi^{e}}_{t}}[{\mathcal{T}}^{{\mathcal{S}}}_{t}(\bar{s})]$
$\displaystyle=0.$ (Recall we derive
$\\{{\mathcal{T}}^{{\mathcal{S}},t}(b_{V})\\}(S^{\diamond}_{t})=0$. )

###  E.2 Proof of Corollary 1

The proof consists of three steps. We use Theorem 4.

##### First step: verify existence of learnable future-dependent value
functions (Show (4a)).

From (LM1), we need to find a solution to

$\displaystyle
w^{\top}_{1}\mathbb{E}[\phi_{\bar{\mathcal{F}}}(\bar{F})\mid\bar{S}]=V^{\pi^{e}}_{t}(\bar{S})$

with respect to a value $w_{1}$. Then, from (LM2f), there exists $w_{2}$ and
$K_{1}$ such that

$\displaystyle
w^{\top}_{1}K_{1}\phi_{\bar{\mathcal{S}}}(\bar{S})=w^{\top}_{2}\phi_{\bar{\mathcal{S}}}(\bar{S}).$

Thus, from (LM3), the above has a solution with respect to $w_{1}$.

##### Second step: verify invertibility condition (Show (4b)).

Take a function $q^{[t]}(\bar{F})$ linear in
$\phi_{\bar{\mathcal{F}}}(\bar{F})$. From (LM1), (LM2) and (LM4), there exists
$w_{3}\in\mathbb{R}^{d_{\bar{\mathcal{S}}}}$ such that

$\displaystyle\mathbb{E}[\mu(Z,O,A)\\{R+\gamma
q^{[t+1]}(\bar{F}^{\prime})-q^{[t]}(\bar{F})\\}\mid\bar{S}]=w^{\top}_{3}\phi_{\bar{\mathcal{S}}}(\bar{S}).$

This is proved as in (28). Then,
$w^{\top}_{3}\mathbb{E}[\phi_{\bar{\mathcal{S}}}(\bar{S})\mid H]=0$ implies
$w^{\top}_{3}\phi_{\bar{\mathcal{S}}}(\bar{S})=0$ from (LM5). Hence, when we
have

$\displaystyle 0$ $\displaystyle=\mathbb{E}[\mathbb{E}[\mu(Z,O,A)\\{R+\gamma
q^{[t+1]}(\bar{F}^{\prime})-q^{[t]}(\bar{F})\\}\mid\bar{S}]\mid H]$
$\displaystyle=\mathbb{E}[w^{\top}_{3}\phi_{\bar{\mathcal{S}}}(\bar{S})\mid
H],$

this implies $w^{\top}_{3}\phi_{\bar{\mathcal{S}}}(\bar{S})=0$, i.e.,

$\mathbb{E}[\mu(Z,O,A)\\{R+\gamma
q^{[t+1]}(\bar{F}^{\prime})-q^{[t]}(\bar{F})\\}\mid\bar{S}]=0.$

##### Third step: show learnable future-dependent value functions are future-
dependent value functions.

Take a learnable future-dependent value function $b_{V}$. Then, from the
condition, we have

$\displaystyle\mathbb{E}[\mu(Z,O,A)\\{R+\gamma
b^{[t+1]}_{V}(\bar{F}^{\prime})\\}-b^{[t]}_{V}(\bar{F})\mid\bar{S}]=0.$

We want to prove

$\displaystyle\mathbb{E}[b^{[t]}_{V}(\bar{F})\mid\bar{S}]=V^{\pi^{e}}_{t}(\bar{S}).$

We use induction. When $t=T-1$, this is clear. Next, supposing the statement
is true at $t+1$, we prove it at a horizon $t$. Here, we have

$\displaystyle\mathbb{E}[b^{[t]}_{V}(\bar{F})\mid\bar{S}]$
$\displaystyle=\mathbb{E}[\mu(Z,O,A)\\{R+\gamma
b^{[t+1]}_{V}(\bar{F}^{\prime})\\}\mid\bar{S}]$
$\displaystyle=\mathbb{E}[\mu(Z,O,A)\\{R+\gamma\mathbb{E}[b^{[t+1]}_{V}(\bar{F}^{\prime})\mid\bar{S}^{\prime}]\\}\mid\bar{S}]$
$\displaystyle=\mathbb{E}[\mu(Z,O,A)\\{R+\gamma
V^{\pi^{e}}_{t+1}(\bar{S}^{\prime})\\}\mid\bar{S}]=V^{\pi^{e}}_{t}(\bar{S}).$

Thus, from induction, we have
$\mathbb{E}[b^{[t]}_{V}(\bar{F})\mid\bar{S}]=V^{\pi^{e}}_{t}(\bar{S})$ for any
$t\in[T-1]$ for any learnable future-dependent value function $b_{V}(\cdot)$.

##### Fourth step: show the final formula.

Recall we define

$\displaystyle\theta_{t}=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]^{+}\mathbb{E}[\mu(Z,O,A)\phi_{\mathcal{H}}(H)\\{R+\gamma\phi^{\top}_{\bar{\mathcal{F}}}(\bar{F}^{\prime})\theta_{t+1}\\}]$

We want to show $\theta^{\top}_{t}\phi_{\bar{\mathcal{F}}}(\cdot)$ is a
learnable future-dependent value function. Here, we need to say

$\displaystyle\mathbb{E}[\mu(Z,O,A)\\{R+\gamma\theta^{\top}_{t+1}\phi_{\bar{\mathcal{F}}}(\bar{F}^{\prime})\\}-\theta^{\top}_{t}\phi_{\bar{\mathcal{F}}}(\bar{F})\mid
H]=0.$

This is satisfied if we have

$\displaystyle\mathbb{E}\left(\phi_{\mathcal{H}}(H)\left(\mu(Z,O,A)\\{R+\gamma\phi^{\top}_{\bar{\mathcal{F}}}(\bar{F}^{\prime})\theta_{t+1}\\}-\phi^{\top}_{\bar{\mathcal{F}}}(\bar{F})\theta_{t}\right)\right)=0.$
(30)

This is because
$\mathbb{E}[\mu(Z,O,A)\\{R+\gamma\theta^{\top}_{t+1}\phi_{\bar{\mathcal{F}}}(\bar{F}^{\prime})\\}-\theta^{\top}_{t}\phi_{\bar{\mathcal{F}}}(\bar{F})\mid
H]=w^{\top}_{5}\phi_{\mathcal{H}}(H)$ for some vector $w_{5}$. Besides,
$\mathbb{E}[w^{\top}_{5}\phi_{\mathcal{H}}(H)\phi_{\mathcal{H}}(H)]=0$ implies
$\mathbb{E}[w^{\top}_{5}\phi_{\mathcal{H}}(H)\phi_{\mathcal{H}}(H)w_{5}]=0$,
which results in

$\displaystyle w^{\top}_{5}\phi_{\mathcal{H}}(H)=0.$

On top of that, since future-dependent value functions
$\langle\tilde{\theta}_{t},\phi_{\bar{\mathcal{F}}}(\bar{F})\rangle$ exist
from the first statement, we have a solution:

$\displaystyle\mathbb{E}\left(\phi_{\mathcal{H}}(H)\left(\mu(Z,O,A)\\{R+\gamma\phi^{\top}_{\bar{\mathcal{F}}}(\bar{F}^{\prime})\tilde{\theta}_{t+1}\\}-\phi^{\top}_{\bar{\mathcal{F}}}(\bar{F})\tilde{\theta}_{t}\right)\right)=0.$

with respect to $\tilde{\theta}_{t}$. In the following, we use this fact.

Now, we go back to the proof of the main statement, i.e., we prove (30). We
use the induction. This is immediately proved when $t=T-1$. Here, suppose
$\phi^{\top}_{\bar{\mathcal{F}}}(\cdot)\theta_{t+1}$ is a learnable future-
dependent value function at $t+1$. Then, we have

$\displaystyle\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]\theta_{t}$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]^{+}\mathbb{E}[\mu(Z,O,A)\phi_{\mathcal{H}}(H)\\{R+\gamma\phi^{\top}_{\bar{\mathcal{F}}}(\bar{F}^{\prime})\theta_{t+1}\\}]$
(Definition)
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]^{+}\mathbb{E}[\mu(Z,O,A)\phi_{\mathcal{H}}(H)\\{R+\gamma
V^{\pi^{e}}_{t+1}(\bar{S}^{\prime})\\}].$

In the last line, we use the inductive hypothesis and the third step. Recall
we showed in the previous step
$\mathbb{E}[b^{[t]}_{V}(\bar{F})\mid\bar{S}]=V^{\pi^{e}}_{t}(\bar{S})$ for any
learnable future-dependent value functions $b^{[t]}_{V}(\cdot)$ . Then, we
have

$\displaystyle\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]\theta_{t}$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]^{+}\mathbb{E}[\mu(Z,O,A)\phi_{\mathcal{H}}(H)\\{R+\gamma
V^{\pi^{e}}_{t+1}(\bar{S}^{\prime})\\}]$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]^{+}\mathbb{E}[\mu(Z,O,A)\phi_{\mathcal{H}}(H)\\{R+\gamma\phi^{\top}_{\bar{\mathcal{F}}}(\bar{F}^{\prime})\tilde{\theta}_{t+1}\\}]$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]^{+}\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]\tilde{\theta}_{t}$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\bar{\mathcal{F}}}(\bar{F})^{\top}]\tilde{\theta}_{t}$
(Property of Moore-Penrose Inverse)
$\displaystyle=\mathbb{E}[\mu(Z,O,A)\phi_{\mathcal{H}}(H)\\{R+\gamma\phi^{\top}_{\bar{\mathcal{F}}}(\bar{F}^{\prime})\tilde{\theta}_{t+1}\\}]$
(Definition of $\tilde{\theta}_{t}$)
$\displaystyle=\mathbb{E}[\mu(Z,O,A)\phi_{\mathcal{H}}(H)\\{R+\gamma
V^{\pi^{e}}_{t+1}(\bar{S}^{\prime})\\}]$ (We showed in the previous step)
$\displaystyle=\mathbb{E}[\mu(Z,O,A)\phi_{\mathcal{H}}(H)\\{R+\gamma\phi^{\top}_{\bar{\mathcal{F}}}(\bar{F}^{\prime})\theta_{t+1}\\}].$
(From the induction)

Hence, $\phi^{\top}_{\bar{\mathcal{F}}}(\cdot)\theta_{t}$ is a learnable
future-dependent value function at $t$.

##  Appendix F Proof of Section 7

###  F.1 Proof of Theorem 5

Then, we have

$\displaystyle J(\pi^{e})$
$\displaystyle=(1-\gamma)^{-1}\mathbb{E}\left[w_{\pi^{e}}(Z,S)\mu(Z,A,O)R\right]$
(Overlap)
$\displaystyle=(1-\gamma)^{-1}\mathbb{E}\left[\mathbb{E}[g_{W}(H)\mid
Z,S]\mu(Z,A,O)R\right]$ (Definition)
$\displaystyle=(1-\gamma)^{-1}\mathbb{E}\left[g_{W}(H)\mu(Z,A,O)R\right]$
($(H\setminus Z)\perp(A,O,R)\mid Z,S$ )
$\displaystyle=(1-\gamma)^{-1}\mathbb{E}\left[g_{W}(H)\left\\{\mathbb{E}[-\mu(Z,A,O)\gamma
b^{\pi^{e}}_{V}(Z^{\prime},F^{\prime})+b^{\pi^{e}}_{V}(Z,F)\mid
H]\right\\}\right].$

In the last line, we use the property of learnable future-dependent value
functions. Then, we have

$\displaystyle J(\pi^{e})$
$\displaystyle=(1-\gamma)^{-1}\mathbb{E}\left[\mathbb{E}[g_{W}(H)\mid
Z,S]\left\\{-\mu(Z,A,O)\gamma
b^{\pi^{e}}_{V}(Z^{\prime},F^{\prime})+b^{\pi^{e}}_{V}(Z,F)\right\\}\right]$
($(H\setminus Z)\perp(A,O,F^{\prime})\mid Z,S$ )
$\displaystyle=(1-\gamma)^{-1}\mathbb{E}\left[w_{\pi^{e}}(Z,S)\left\\{-\mu(Z,A,O)\gamma
b^{\pi^{e}}_{V}(Z^{\prime},F^{\prime})+b^{\pi^{e}}_{V}(Z,F)\right\\}\right]$ (
Definition)
$\displaystyle=(1-\gamma)^{-1}\mathbb{E}\left[w_{\pi^{e}}(Z,S)\left\\{-\mu(Z,A,O)\gamma\mathbb{E}[b^{\pi^{e}}_{V}(Z^{\prime},F^{\prime})\mid
Z^{\prime},S^{\prime}]+\mathbb{E}[b^{\pi^{e}}_{V}(Z,F)\mid
Z,S]\right\\}\right]$ ( $F^{\prime}\perp(Z\setminus Z^{\prime}),S,A,O\mid
Z^{\prime},S^{\prime}$)
$\displaystyle=\mathbb{E}_{\bar{s}\sim\nu_{\bar{S}}}[\mathbb{E}[b^{\pi^{e}}_{V}(\bar{F})\mid\bar{S}=s]]$
( Lemma 11)
$\displaystyle=\mathbb{E}_{\bar{f}\sim\nu_{\bar{\mathcal{F}}}}[b^{\pi^{e}}_{V}(\bar{f})].$
(Definition)

###  F.2 Proof of Theorem 6

From Hoeffeding inequality, we use with probability $1-\delta$,

$\displaystyle\forall\alpha_{1}\in\Xi,\forall\alpha_{2}\in\mathcal{G};|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})[\alpha_{1}(H)(\mathcal{Z}\alpha_{2})(Z,R,A,O,F^{\prime})]|\leq
c{\max(1,C_{\Xi},C_{\mathcal{G}})\sqrt{\ln(|\mathcal{G}||\Xi|)/n}}$

where
$\mathcal{Z}:\alpha_{2}(\cdot)\mapsto\mu(z,a,o)\\{r-\alpha_{2}(z,f)\\}+\gamma\alpha_{2}(z^{\prime},f^{\prime})$.
Hereafter, we condition on the above event. In this proof, we often use the
following

$\displaystyle\mathbb{E}[\alpha_{1}(H)(\mathcal{Z}\alpha_{2})(Z,R,A,O,F^{\prime})]=\mathbb{E}[\alpha_{1}(H)({\mathcal{T}}\alpha_{2})(H)].$

As a first step, following the proof of Theorem 5, we have

$\displaystyle|J(\pi^{e})-\hat{J}_{\mathrm{VM}}|\leq|(1-\gamma)^{-1}\mathbb{E}[g_{W}(H)\mathcal{Z}\hat{b}_{V}(Z,A,O,R,F^{\prime})]|.$

Here, we further have

$\displaystyle|\mathbb{E}[g_{W}(H)\mathcal{Z}\hat{b}_{V}(Z,A,O,R,F^{\prime})]|$
$\displaystyle\leq|\mathbb{E}-\mathbb{E}_{\mathcal{D}})[g_{W}(H)\mathcal{Z}\hat{b}_{V}(Z,A,O,R,F^{\prime})]|+|\mathbb{E}_{\mathcal{D}}[g_{W}(H)\mathcal{Z}\hat{b}_{V}(Z,A,O,R,F^{\prime})]|$
$\displaystyle\leq
c{\max(1,C_{\Xi},C_{\mathcal{G}})\sqrt{\ln(|\mathcal{G}||\Xi|)/n}}+\sup_{\alpha_{2}\in\Xi}|\mathbb{E}_{\mathcal{D}}[\alpha_{2}(H)\mathcal{Z}\hat{b}_{V}(Z,A,O,R,F^{\prime})]|$
( $g_{W}\in\Xi$) $\displaystyle\leq
c{\max(1,C_{\Xi},C_{\mathcal{G}})\sqrt{\ln(|\mathcal{G}||\Xi|)/n}}+\sup_{\alpha_{2}\in\Xi}|\mathbb{E}_{\mathcal{D}}[\alpha_{2}(H)\mathcal{Z}b^{\pi^{e}}_{V}(Z,A,O,R,F^{\prime})]|$
($b_{V}\in\mathcal{G}$ )
$\displaystyle\leq(c+c_{1}){\max(1,C_{\Xi},C_{\mathcal{G}})\sqrt{\ln(|\mathcal{G}||\Xi|)/n}}.$

In the final line, we use

$\displaystyle\sup_{\alpha_{2}\in\Xi}|\mathbb{E}_{\mathcal{D}}[\alpha_{2}(H)\mathcal{Z}b^{\pi^{e}}_{V}(Z,A,O,R,F^{\prime})]|\leq
c_{1}{\max(1,C_{\Xi},C_{\mathcal{G}})\sqrt{\ln(|\mathcal{G}||\Xi|)/n}}.$

which is proved by

$\displaystyle\sup_{\alpha_{2}\in\Xi}|\mathbb{E}_{\mathcal{D}}[\alpha_{2}(H)\mathcal{Z}b^{\pi^{e}}_{V}(Z,A,O,R,F^{\prime})]|$
$\displaystyle=|\mathbb{E}_{\mathcal{D}}[\alpha^{\diamond}_{2}(H)\mathcal{Z}b^{\pi^{e}}_{V}(Z,A,O,R,F^{\prime})]|$
$\displaystyle\leq|\mathbb{E}[\alpha^{\diamond}_{2}(H)\mathcal{Z}b^{\pi^{e}}_{V}(Z,A,O,R,F^{\prime})]|+c_{1}{\max(1,C_{\Xi},C_{\mathcal{G}})\sqrt{\ln(|\mathcal{G}||\Xi|)/n}}$
$\displaystyle=|\mathbb{E}[\alpha^{\diamond}_{2}(H){\mathcal{T}}b^{\pi^{e}}_{V}(H)]|+c_{1}{\max(1,C_{\Xi},C_{\mathcal{G}})\sqrt{\ln(|\mathcal{G}||\Xi|)/n}}$
$\displaystyle=c_{1}{\max(1,C_{\Xi},C_{\mathcal{G}})\sqrt{\ln(|\mathcal{G}||\Xi|)/n}}.$

###  F.3 Proof of Theorem 7

Note for any $b_{V}\in\mathcal{B}^{\Xi}_{V}\cap\mathcal{Q}$, from (7b), we
have

$\displaystyle\mathbb{E}[b_{V}(Z,F)\mid
Z,S]=\mathbb{E}\left[\mu(Z,A,O)\left(R+\gamma
b_{V}(Z^{\prime},F^{\prime})\right)\mid Z,S\right].$ (31)

Hence, ${\mathcal{T}}^{{\mathcal{S}}}(b_{V})(\bar{S})=0.$ Then, from the
overlap condition (2c),

$\displaystyle{\mathcal{T}}^{{\mathcal{S}}}(b_{V})(\bar{S}^{\diamond})=0.$
(32)

Finally, for any $b_{V}\in\mathcal{B}^{\Xi}_{V}\cap\mathcal{Q}$, we have

$\displaystyle(J(\pi^{e})-\mathbb{E}_{\bar{f}\sim\nu_{\bar{\mathcal{F}}}}[b_{V}(\bar{f})])$
$\displaystyle=(1-\gamma)^{-1}\mathbb{E}_{(\tilde{s})\sim
d_{\pi^{e}}}\left[\mathbb{E}[\mu(Z,A,O)R\mid\bar{S}=\tilde{s}]\right]-\mathbb{E}_{\bar{f}\sim\nu_{\bar{\mathcal{F}}}}[b_{V}(\bar{f})]$
$\displaystyle=(1-\gamma)^{-1}\mathbb{E}_{(\tilde{s})\sim
d_{\pi^{e}}}\left[\mathbb{E}\left[\mu(Z,A,O)\\{R+\gamma
b_{V}(Z^{\prime},F^{\prime})\\}-b_{V}(Z,F)\mid\bar{S}=\tilde{s}\right]\right]$
(Use Lemma 11) $\displaystyle=0.$ (Use
${\mathcal{T}}^{{\mathcal{S}}}(S^{\diamond})=0.$)

###  F.4 Proof of Theorem 8

We want to prove

$\displaystyle\sup_{\xi\in\Xi}|\mathbb{E}[\\{{\mathcal{T}}^{{\mathcal{S}}}\hat{b}_{V}\\}(\bar{S})\xi(H)]|\leq\sqrt{\ln(|\mathcal{G}||\Xi|/\delta)/n}.$

This is proved as

$\displaystyle\sup_{\xi\in\Xi}|\mathbb{E}[\\{{\mathcal{T}}^{{\mathcal{S}}}\hat{b}_{V}\\}(\bar{S})\xi(H)]|$
$\displaystyle=\sup_{\xi\in\Xi}|\mathbb{E}[\\{\mathcal{Z}\hat{b}_{V}\\}(H)\xi(H)]|$
$\displaystyle\leq\sup_{\xi\in\Xi}|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})[\\{\mathcal{Z}\hat{b}_{V}\\}(H)\xi(H)]|+\sup_{\xi\in\Xi}|\mathbb{E}_{\mathcal{D}}[\\{\mathcal{Z}\hat{b}_{V}\\}(H)\xi(H)]|$
(Triangle inequality)
$\displaystyle\leq\sup_{\xi\in\Xi}|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})[\\{\mathcal{Z}\hat{b}_{V}\\}(H)\xi(H)]|+\sup_{\xi\in\Xi}|\mathbb{E}_{\mathcal{D}}[\\{\mathcal{Z}b_{V}\\}(H)\xi(H)]|$
( $b_{V}\in\mathcal{G}$)
$\displaystyle\leq\sup_{\xi\in\Xi}|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})[\\{\mathcal{Z}\hat{b}_{V}\\}(H)\xi(H)]|+\sup_{\xi\in\Xi}|(\mathbb{E}-\mathbb{E}_{\mathcal{D}})[\\{\mathcal{Z}b_{V}\\}(H)\xi(H)]|+\sup_{\xi\in\Xi}|\mathbb{E}[\\{\mathcal{Z}b_{V}\\}(H)\xi(H)]|$
$\displaystyle\leq c\sqrt{\ln(|\mathcal{G}||\Xi|/\delta)/n}.$

Then, we have

$\displaystyle(J(\pi^{e})-\mathbb{E}_{\bar{f}\sim\nu_{\bar{\mathcal{F}}}}[\hat{b}_{V}(\bar{f})])^{2}$
$\displaystyle=\left\\{(1-\gamma)^{-1}\mathbb{E}_{(\tilde{s})\sim
d_{\pi^{e}}}\left[\mathbb{E}[\mu(Z,A,O)R\mid\bar{S}=\tilde{s}]\right]-\mathbb{E}_{\bar{f}\sim\nu_{\bar{\mathcal{F}}}}[\hat{b}_{V}(\bar{f})]\right\\}^{2}$
$\displaystyle=\left\\{(1-\gamma)^{-1}\mathbb{E}_{(\tilde{s})\sim
d_{\pi^{e}}}\left[\mathbb{E}\left[\mu(Z,A,O)\\{R+\gamma\hat{b}_{V}(Z^{\prime},F^{\prime})\\}-\hat{b}_{V}(Z,F)\mid\bar{S}=\tilde{s}\right]\right]\right\\}^{2}$
(Use Lemma 11)
$\displaystyle\leq(1-\gamma)^{-2}\mathbb{E}[\\{{\mathcal{T}}^{{\mathcal{S}}}(\hat{b}_{V})\\}^{2}(\bar{s})]$
(Jensen’s inequality)
$\displaystyle\leq(1-\gamma)^{-2}\\{\sup_{\xi\in\Xi}|\mathbb{E}[\\{{\mathcal{T}}^{{\mathcal{S}}}\hat{b}_{V}\\}(\bar{S})\xi(H)]|\\}^{2}\times\sup_{q\in\mathcal{Q}}\frac{\mathbb{E}_{\bar{s}\sim
d_{\pi^{e}}}[({\mathcal{T}}^{{\mathcal{S}}}q)^{2}(\bar{s})]}{\\{\sup_{\xi\in\Xi}|\mathbb{E}[\\{{\mathcal{T}}^{{\mathcal{S}}}\hat{b}_{V}\\}(\bar{S})\xi(H)]|\\}^{2}}.$

Hence, the statement is proved.

###  F.5 Proof of Lemma 10

The proof consists of three steps. We invoke Theorem 7.

##### First step: verify (7a).

Refer to the proof of Lemma 5.

##### Second step: verify (7b).

From (LM1), (LM4) and the above statement, there exists
$w_{4}\in\mathbb{R}^{d_{\bar{\mathcal{S}}}}$ such that

$\displaystyle\mathbb{E}[\mu(Z,O,A)\\{R+\gamma
q(Z^{\prime},F^{\prime})\\}-q(Z,F)\mid
Z,S]=w^{\top}_{4}\phi_{\bar{\mathcal{S}}}(\bar{S}).$

for any $q(\cdot)=w^{\top}\phi_{\bar{\mathcal{F}}}(\cdot)\in\mathcal{Q}$
following (28).

Then, from (LMW5), when
$w^{\top}_{4}\mathbb{E}[\phi_{\bar{\mathcal{S}}}(\bar{S})\phi_{\mathcal{H}}(H)]=0$,
this implies $w^{\top}_{4}\phi_{\bar{\mathcal{S}}}(\bar{S})=0$.

Here, noting

$\displaystyle 0$ $\displaystyle=\mathbb{E}[\mathbb{E}[\mu(Z,O,A)\\{R+\gamma
q(Z^{\prime},F^{\prime})\\}-q(Z,F)\mid Z,S]\xi(H)]$
$\displaystyle=\mathbb{E}[w^{\top}_{4}\phi_{\bar{\mathcal{S}}}(\bar{S})\xi(H)].$
(Just plug-in)

Thus, we get $w^{\top}_{4}\phi_{\bar{\mathcal{S}}}(\bar{S})=0$, i.e.,

$\displaystyle\mathbb{E}[\mu(Z,O,A)\\{R+\gamma
q(Z^{\prime},F^{\prime})\\}-q(Z,F)\mid Z,S]=0.$

##### Final part.

Let

$\displaystyle\tilde{w}=\mathbb{E}[\phi_{\mathcal{H}}(H)\\{\gamma\phi_{\bar{\mathcal{F}}}(\bar{F}^{\prime})-\phi_{\bar{\mathcal{F}}}(\bar{F})\\}]^{+}\mathbb{E}[\mu(Z,O,A)R\phi_{\mathcal{H}}(H)].$

In the proof of Lemma 7, we already saw

$\displaystyle\mathbb{E}[\phi_{\mathcal{H}}(H)\\{\gamma\mu(Z,O,A)\phi_{\bar{\mathcal{F}}}(\bar{F}^{\prime})-\phi_{\bar{\mathcal{F}}}(\bar{F})\\}^{\top}]\tilde{w}=\mathbb{E}[\mu(Z,O,A)R\phi_{\mathcal{H}}(H)]$

The above is a sufficient condition to ensure
$w^{\top}\phi_{\bar{\mathcal{F}}}(\cdot)$ belongs to
$\mathcal{B}^{\Xi}_{V}\cap\mathcal{Q}$. Then, by invoking Theorem 7, the
statement is concluded.

##  Appendix G Proof of Section 8

###  G.1 Proof of Theorem 9

We take a value bridge function
$b^{[t]}_{D}\in\mathcal{Q}_{t}\cap\mathcal{B}^{[t]}_{\mathcal{D}}$ for any
$[T]$. Then, we define

$\displaystyle l^{[t]}_{D}(\cdot)=\mathbb{E}[b^{[t]}_{D}(F)\mid S=\cdot].$

In this section, $\mathbb{E}[\cdot\,;A_{0:T-1}\sim\pi^{e}]$ means taking
expectation when we execute a policy $\pi_{e}$ from $t=0$ to $T-1$. Note
$\mathbb{E}[\cdot\,;A_{0:T-1}\sim\pi^{b}]$ is just $\mathbb{E}[\cdot]$. Here,
we have

$\displaystyle\mathrm{Pr}_{\pi^{e}}(o_{0},a_{0},\cdots,a_{T-1})-\mathbb{E}_{f\sim\nu_{\mathcal{F}}}[b^{[0]}_{D}(f)]$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{E}\left[\left\\{\prod_{k=0}^{t-1}\mathrm{I}(O_{k}=o_{k},A_{k}=a_{k})\right\\}\left\\{\mathrm{I}(O_{t}=o_{t},A_{t}=a_{t})l^{[t+1]}_{D}(S_{t+1})-l^{[t]}_{D}(S_{t})\right\\};A_{0:T-1}\sim\pi^{e}\right]$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{E}[\left\\{\prod_{k=0}^{t-1}\mathrm{I}(O_{k}=o_{k},A_{k}=a_{k})\right\\}\\{\mathbb{E}[\mathrm{I}(O_{t}=o_{t},A_{t}=a_{t})l^{[t+1]}_{D}(S_{t+1})\mid
S_{t},(O_{0},A_{0},\cdots,A_{t-1})=(o_{0},a_{0},\cdots,a_{t-1})]$
$\displaystyle-l^{[t]}_{D}(S_{t})\\};A_{0:T-1}\sim\pi^{e}]$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{E}\left[\left\\{\prod_{k=0}^{t-1}\mathrm{I}(O_{k}=o_{k},A_{k}=a_{k})\right\\}\left\\{\mathbb{E}[\mathrm{I}(O_{t}=o_{t},A_{t}=a_{t})l^{[t+1]}_{D}(S_{t+1})\mid
S_{t}]-l^{[t]}_{D}(S_{t})\right\\};A_{0:T-1}\sim\pi^{e}\right].$

In the first line, we use a telescoping sum trick noting

$\displaystyle\mathrm{Pr}_{\pi^{e}}(o_{0},a_{0},\cdots,a_{T-1})=\mathbb{E}\left[\prod_{k=0}^{T-1}\mathrm{I}(O_{k}=o_{k},A_{k}=a_{k});A_{0:T-1}\sim\pi^{e}\right].$

From the second line to the third line, we use $S_{t+1},O_{t},A_{t}\perp
O_{1},\cdots,A_{t}\mid S_{t}$.

Here, we have

$\displaystyle\mathbb{E}[\mathrm{I}(O_{t}=o_{t},A_{t}=a_{t})l^{[t+1]}_{D}(S_{t+1})\mid
S_{t};A_{t}\sim\pi^{e}]=\tilde{l}^{[t]}_{D}(S_{t})$

where
$\tilde{l}^{[t+1]}_{D}(\cdot)=\mathbb{E}[\mathrm{I}(O=o_{t},A=a_{t})\mu(O,A)l^{[t+1]}_{D}(S^{\prime})\mid
S=\cdot;A_{t}\sim\pi^{b}]$ using importance sampling. Hence, the following
holds:

$\displaystyle\mathrm{Pr}_{\pi^{e}}(o_{0},a_{0},\cdots,a_{T-1})-\mathbb{E}_{f\sim\nu_{\mathcal{F}}}[b^{[0]}_{D}(f)]$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{E}\left[\left\\{\prod_{k=0}^{t-1}\mathrm{I}(O_{k}=o_{k},A_{k}=a_{k})\right\\}\left\\{\tilde{l}^{[t+1]}_{D}(S_{t})-l^{[t]}_{D}(S_{t})\right\\};A_{0:T-1}\sim\pi^{e}\right]$
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{E}\left[\left\\{\prod_{k=0}^{t-1}\mathrm{I}(O_{k}=o_{k},A_{k}=a_{k})({\mathcal{T}}^{{\mathcal{S}}}_{t}b_{D})(S_{t})\right\\};A_{0:T-1}\sim\pi^{e}\right]$
(33)
$\displaystyle=\sum_{t=0}^{T-1}\mathbb{E}\left[\left\\{\prod_{k=0}^{t-1}\mathrm{I}(O_{k}=o_{k},A_{k}=a_{k})\mathbb{E}[({\mathcal{T}}^{{\mathcal{S}}}_{t}b_{D})(S_{t})\mid(O_{1},A_{1},\cdots,A_{K})=(o_{1},a_{1},\cdots,o_{K})]\right\\};A_{0:T-1}\sim\pi^{e}\right]$
(34)

From the second line to the third line, we use

$\displaystyle\mathbb{E}[\mathrm{I}(O=o_{t},A=a_{t})\mu(O,A)l^{[t+1]}_{D}(S^{\prime})\mid
S]$
$\displaystyle=\mathbb{E}[\mathrm{I}(O=o_{t},A=a_{t})\mu(O,A)\mathbb{E}[b^{[t+1]}_{D}(F^{\prime})\mid
S^{\prime}]\mid S]$ (Definition)
$\displaystyle=\mathbb{E}[\mathrm{I}(O=o_{t},A=a_{t})\mu(O,A)\mathbb{E}[b^{[t+1]}_{D}(F^{\prime})\mid
S^{\prime},O=o_{t},A=a_{t}]\mid S]$ (Low of total expectation)
$\displaystyle=\mathbb{E}[\mathrm{I}(O=o_{t},A=a_{t})\mu(O,A)b^{[t+1]}_{D}(F^{\prime})\mid
S].$ ($F^{\prime}\perp O,A\mid S^{\prime}$ )

Besides, we know for any learnable bridge function $b_{D}$, we have

$\displaystyle\mathbb{E}[\mathrm{I}(O=o_{t},A=a_{t})\mu(O,A)b^{[t+1]}_{D}(F^{\prime})-b^{[t]}_{D}(F)\mid
H]=0.$

Then, since

$\displaystyle\mathbb{E}[\mathbb{E}[\mathrm{I}(O=o_{t},A=a_{t})\mu(O,A)b^{[t+1]}_{D}(F^{\prime})-b^{[t]}_{D}(F)\mid
S]\mid H]=0$

from the invertibility condition (b), we have

$\displaystyle\mathbb{E}[\mathrm{I}(O=o_{t},A=a_{t})\mu(O,A)b^{[t+1]}_{D}(F^{\prime})-b^{[t]}_{D}(F)\mid
S]=0.$

From the overlap (c), this implies

$\displaystyle({\mathcal{T}}^{{\mathcal{S}}}_{t}b_{D})(\grave{S}_{t})=0.$

Finally, from (34), we can conclude
$\mathrm{Pr}_{\pi^{e}}(o_{0},a_{0},\cdots,a_{T-1})-\mathbb{E}_{f\sim\nu_{\mathcal{F}}}[b^{[0]}_{D}(f)]=0$.

###  G.2 Proof of Theorem 10

This is proved as in Theorem 9 noting

$\displaystyle\mathrm{Pr}_{\pi^{e}}(o_{0},a_{0},\cdots,a_{T-1},\mathbf{O}_{T})=\mathbb{E}\left[\phi_{\mathcal{O}}(O_{T})\prod_{k=0}^{T-1}\mathrm{I}(O^{\diamond}_{k}=o_{k},A^{\diamond}_{k}=a_{k})\right].$

###  G.3 Proof of Corollary 2

This is proved following Corollary 3.

###  G.4 Proof of Corollary 3

The proof consists of four steps. The proof largely follows the proof of
Corollary 1.

##### First step: verify the existence of bridge functions (9a).

We show there exists a bridge function linear in $\phi_{\mathcal{F}}(F)$. We
need to find a solution to $w^{\top}_{1}\mathbb{E}[\phi_{\mathcal{F}}(F)\mid
S]=V^{\pi^{e}}_{D,[t]}(S)$ with respect to $w_{1}$. Then, from (LM2D), there
exists $w_{2}$ and $K_{1}$ such that

$\displaystyle
w^{\top}_{1}K_{1}\phi_{{\mathcal{S}}}(S)=w^{\top}_{2}\phi_{{\mathcal{S}}}(S).$

Thus, from (LM3), the above has a solution with respect to $w_{1}$.

##### Second step: verify invertibility conditions (9b).

We take $\mathcal{Q}_{t}$ to be a linear model in $\phi_{\mathcal{F}}(F)$. For
$q^{[t]}_{D}\in\mathcal{Q}_{t}$, from (LM1), (LM2), (LM4), there exists
$w_{3}\in\mathbb{R}^{d_{{\mathcal{S}}}}$ such that

$\displaystyle\mathbb{E}[q^{[t]}_{D}(F)-\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)q^{[t+1]}_{D}(F^{\prime})\mid
S]=w^{\top}_{3}\phi_{{\mathcal{S}}}(S).$

Then, $w^{\top}_{3}\mathbb{E}[\phi_{{\mathcal{S}}}(S)\mid H]=0$ implies
$w^{\top}_{3}\phi_{{\mathcal{S}}}(S)=0$ from (LM5). Hence,

$\displaystyle 0$
$\displaystyle=\mathbb{E}[q^{[t]}_{D}(F)-\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)q^{[t+1]}_{D}(F^{\prime})\mid
H]$
$\displaystyle=\mathbb{E}[\mathbb{E}[q^{[t]}_{D}(F)-\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)q^{[t+1]}_{D}(F^{\prime})\mid
S]\mid H]$

implies
$\mathbb{E}[q^{[t]}_{D}(F)-\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)q^{[t+1]}_{D}(F^{\prime})\mid
S]=0$. Thus, the invertibility is concluded.

##### Third step: show learnable value bridge functions are value bridge
functions.

From the previous discussion, learnable value bridge functions in
$\mathcal{Q}$ need to satisfy

$\displaystyle
0=\mathbb{E}[b^{[t]}_{D}(F)-\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)b^{[t+1]}_{D}(F^{\prime})\mid
S].$

Here, we want to prove

$\displaystyle\mathbb{E}[b^{[t]}_{D}(F)\mid S]=V^{\pi^{e}}_{D,[t]}(S).$

We use induction. When $t=T-1$, this is clear. Next, supposing the statement
is true at $t+1$, we prove it at horizon $t$. Here, we have

$\displaystyle\mathbb{E}[b^{[t]}_{D}(F)\mid S]$
$\displaystyle=\mathbb{E}[\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)b^{[t+1]}_{D}(F^{\prime})\mid
S]$
$\displaystyle=\mathbb{E}[\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)\mathbb{E}[b^{[t+1]}_{D}(F^{\prime})\mid
S^{\prime}]\mid S]$
$\displaystyle=\mathbb{E}[\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)V^{\pi^{e}}_{D,[t+1]}(S^{\prime})\mid
S]$ $\displaystyle=V^{\pi^{e}}_{D,[t]}(S).$

##### Fourth step: show the final formula.

We recursively define

$\displaystyle\theta^{\top}_{t}=\theta^{\top}_{t+1}D_{t}B^{+}.$

starting from $\tilde{w}^{\top}_{T}B=\mathbb{E}[\phi_{\mathcal{H}}(H)].$ We
want to show $\theta^{\top}_{t}\phi_{\mathcal{F}}(\cdot)$ is a learnable value
bridge function. Here, we want to say

$\displaystyle\mathbb{E}[\theta^{\top}_{t}\phi_{\mathcal{F}}(F)-\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)\theta^{\top}_{t+1}\phi_{\mathcal{F}}(F^{\prime})\mid
H]=0.$

This is satisfied if we have

$\displaystyle\mathbb{E}\left[\left(\theta^{\top}_{t}\phi_{\mathcal{F}}(F)-\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)\theta^{\top}_{t+1}\phi_{\mathcal{F}}(F^{\prime})\right)\phi_{\mathcal{H}}(H)\right]=0$

Here, refer to the fourth step in the proof of Corollary 1. Besides, as we
already show linear value bridge functions exist
$\langle\tilde{\theta}_{t},\phi_{\mathcal{F}}(\cdot)\rangle$, we have a
solution to:

$\displaystyle\mathbb{E}\left[\left(\tilde{\theta}^{\top}_{t}\phi_{\mathcal{F}}(F)-\mathbb{I}(O=o_{t},A=a_{t})\mu(O,A)\tilde{\theta}^{\top}_{t+1}\phi_{\mathcal{F}}(F^{\prime})\right)\phi_{\mathcal{H}}(H)\right]=0$

with respect to $\tilde{\theta}_{t}$.

Hereafter, we use the induction. This is immediately proved when $t=T-1$.
Here, suppose $\phi^{\top}_{\mathcal{F}}(F)\theta_{t+1}$ is a learnable value
bridge function at $t+1$. Then, we have

$\displaystyle\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]\theta_{t}$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]^{+}D^{\top}_{t}\theta_{t+1}$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]^{+}\mathbb{E}[\mathrm{I}(O=O_{t},A=a_{t})\mu(O,A)\phi_{\mathcal{H}}(H)\phi^{\top}_{\mathcal{F}}(F^{\prime})\theta_{t+1}]$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]^{+}\mathbb{E}[\mathrm{I}(O=O_{t},A=a_{t})\mu(O,A)\phi_{\mathcal{H}}(H)V^{\pi^{e}}_{D,[t+1]}(S^{\prime})].$

In the last line, we use inductive hypothesis. We showed in the previous step
$\mathbb{E}[b^{[t]}_{D}(F)\mid S]=V^{\pi^{e}}_{D,[t]}(S)$ for any learnable
value bridge function $b^{[t]}_{D}(F)$. Then, we have

$\displaystyle\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]^{+}\mathbb{E}[\mathrm{I}(O=O_{t},A=a_{t})\mu(O,A)\phi_{\mathcal{H}}(H)V^{\pi^{e}}_{D,[t+1]}(S^{\prime})]$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]^{+}\mathbb{E}[\mathrm{I}(O=O_{t},A=a_{t})\mu(O,A)\phi_{\mathcal{H}}(H)\\{\phi^{\top}_{\mathcal{F}}(F^{\prime})\tilde{\theta}_{t+1}\\}]$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]^{+}\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]\tilde{\theta}_{t}$
$\displaystyle=\mathbb{E}[\phi_{\mathcal{H}}(H)\phi_{\mathcal{F}}(F)^{\top}]\tilde{\theta}_{t}$
(Property of Moore-Penrose Inverse)
$\displaystyle=\mathbb{E}[\mathrm{I}(O=O_{t},A=a_{t})\mu(O,A)\phi_{\mathcal{H}}(H)V^{\pi^{e}}_{D,[t+1]}(S^{\prime})]$
(We show in the previous step)
$\displaystyle=\mathbb{E}[\mathrm{I}(O=O_{t},A=a_{t})\mu(O,A)\phi_{\mathcal{H}}(H)\\{\phi^{\top}_{\mathcal{F}}(F^{\prime})\theta_{t+1}\\}].$
(From the induction)

So far, we prove $\theta^{\top}_{t}\phi_{\mathcal{F}}(\cdot)$ is a learnable
value bridge function for $t$. Finally, by consdiering a time-step $t=0$, we
can prove the target estimand is

$\displaystyle\mathbb{E}[\tilde{w}^{\top}_{0}\phi_{\mathcal{F}}(F)]=\mathbb{E}[\phi_{\mathcal{H}}(H)]^{\top}B^{+}\left\\{\prod^{0}_{t=T-1}D_{t}B^{+}\right\\}C.$

##  Appendix H Auxiliary Lemmas

######  Lemma 11.

Take $g\in[\bar{\mathcal{S}}\to\mathbb{R}]$. Then, we have

$\displaystyle 0=(1-\gamma)^{-1}\mathbb{E}_{\bar{s}\sim
d_{\pi^{e}}}\left[\mathbb{E}[\mu(Z,O,A)\gamma
g(\bar{S}^{\prime})-g(\bar{S})\mid\bar{S}=\bar{s}]\right]+\mathbb{E}_{\bar{s}\sim\nu_{\bar{S}}}[g(\bar{s})].$

###### Proof.

Let $d_{\pi^{e}}(z,s)=d^{\pi^{e}}_{0}(\cdot)$. Then, we have

$\displaystyle\int g(z,s)d_{\pi^{e}}(z,s)d(z,s)$ $\displaystyle=(1-\gamma)\int
g(z,s)\sum_{t=0}^{\infty}\gamma^{t}d^{\pi^{e}}_{t}(z,s)d(z,s)$
$\displaystyle=\underbrace{(1-\gamma)\int
g(z,s)d^{\pi^{e}}_{0}(z,s)d(z,s)}_{(a)}+\underbrace{\gamma(1-\gamma)\int
g(z^{\prime},s^{\prime})\sum_{t=1}^{\infty}\gamma^{t-1}d^{\pi^{e}}_{t}(z^{\prime},s^{\prime})d(z^{\prime},s^{\prime})}_{(b)}.$

We analyze the first term (a) and the second term (b). The first term (a) is
$\mathbb{E}_{\bar{s}\sim\nu_{\bar{S}}}[g(\bar{s})].$ In the following, we
analyze the second term.

Here, note

$\displaystyle
d^{\pi^{e}}_{t}(z^{\prime},s^{\prime})=\int\mathbb{T}(s^{\prime}\mid
s,a)\mathbb{O}(o\mid s)\pi^{e}(a\mid
z,o)\delta^{\dagger}(z^{\prime}=z)d^{\pi^{e}}_{t-1}(z,s)d(z,s).$

where $\delta^{\dagger}(z^{\prime}=z)=\delta(f_{-1}(z^{\prime})=f_{+1}(z))$.
Here, $f_{-1}$ is a transformation removing the most recent tuple $(o,a,r)$
and $f_{+1}$ is a transformation removing the oldest tuple $(o,a,r)$. Hence,

$\displaystyle(1-\gamma)\sum_{t=1}^{\infty}\gamma^{t-1}d^{\pi^{e}}_{t}(z^{\prime},s^{\prime})$
$\displaystyle=(1-\gamma)\int\sum_{t=1}^{\infty}\gamma^{t-1}\mathbb{T}(s^{\prime}\mid
s,a)\mathbb{O}(o\mid s)\pi^{e}(a\mid
z,o)\delta^{\dagger}(z^{\prime}=z)d^{\pi^{e}}_{t-1}(z,s)d(z,s)$
$\displaystyle=(1-\gamma)\int\sum_{k=0}^{\infty}\gamma^{k}\mathbb{T}(s^{\prime}\mid
s,a)\mathbb{O}(o\mid s)\mu(z,o,a)\pi^{b}(a\mid
z,o)\delta^{\dagger}(z^{\prime}=z)d^{\pi^{e}}_{k}(z,s)d(z,s)$
$\displaystyle=\int\mathbb{T}(s^{\prime}\mid s,a)\mathbb{O}(o\mid
s)\mu(z,o,a)\pi^{b}(a\mid
z,o)\delta^{\dagger}(z^{\prime}=z)d^{\pi^{e}}(z,s)d(z,s).$

Therefore, the term (b) is

$\displaystyle\gamma(1-\gamma)\int
g(z^{\prime},s^{\prime})\sum_{t=1}^{\infty}\gamma^{t-1}d^{\pi^{e}}_{t}(z^{\prime},s^{\prime})d(z^{\prime},s^{\prime})$
$\displaystyle=\gamma\int g(z^{\prime},s^{\prime})\mathbb{T}(s^{\prime}\mid
s,a)\mathbb{O}(o\mid s)\mu(z,o,a)\pi^{b}(a\mid
z,o)\delta^{\dagger}(z^{\prime}=z)d^{\pi^{e}}(z,s)d(z,z^{\prime},s,s^{\prime})$
$\displaystyle=\gamma\mathbb{E}_{\bar{s}\sim
d_{\pi^{e}}}\left[\mathbb{E}[\mu(Z,O,A)\gamma
g(\bar{S}^{\prime})\mid\bar{S}=\bar{s}]\right].$

∎