# Strong and Efficient Baselines for
Open Domain Conversational Question Answering

Andrei C. Coman
Idiap Research Institute, EPFL
<EMAIL_ADDRESS>
&Gianni Barlacchi
Amazon Alexa AI
<EMAIL_ADDRESS>&Adrià de Gispert
Amazon Alexa AI
<EMAIL_ADDRESS>Work was done during an internship at Amazon Science.

###### Abstract

Unlike the Open Domain Question Answering (ODQA) setting, the conversational
(ODConvQA) domain has received limited attention when it comes to reevaluating
baselines for both efficiency and effectiveness. In this paper, we study the
State-of-the-Art (SotA) Dense Passage Retrieval (DPR) retriever and Fusion-in-
Decoder (FiD) reader pipeline, and show that it significantly underperforms
when applied to ODConvQA tasks due to various limitations. We then propose and
evaluate strong yet simple and efficient baselines, by introducing a fast
reranking component between the retriever and the reader, and by performing
targeted finetuning steps. Experiments on two ODConvQA tasks, namely TopiOCQA
and OR-QuAC, show that our method improves the SotA results, while reducing
reader’s latency by 60%. Finally, we provide new and valuable insights into
the development of challenging baselines that serve as a reference for future,
more intricate approaches, including those that leverage Large Language Models
(LLMs).

##  1 Introduction

Figure 1: The Retriever-Reranker-Reader (R3) pipeline

In an automated information-seeking conversation scenario between two parties,
the human questioner asks a series of questions and expects to receive a
relevant response from the answering system (Oddy, 1977). Current State-of-
the-Art (SotA) shapes the answerer via two neural models, the Dense Passage
Retrieval (DPR) (Karpukhin et al., 2020) and the Fusion-in-Decoder (FiD)
(Izacard and Grave, 2021b), which act as retriever and reader, respectively.
Their success stems from the ability to overcome certain limitations of their
sparse and extractive counterparts, such as not relying on lexical retrieval
heuristics or extracting spans as a response (Chen et al., 2017; Yang et al.,
2019; Lee et al., 2019; McCallum et al., 2019; Guu et al., 2020; Lewis et al.,
2020; Shen et al., 2023). Among the most promising approaches are those
concerning the improvement of training strategies (Guu et al., 2020;
Balachandran et al., 2021; Qu et al., 2021), use of rerankers (Hu et al.,
2019; Mao et al., 2021; Barlacchi et al., 2022; Iyer et al., 2021; Glass et
al., 2022), question rewriting (Vakulenko et al., 2021; Del Tredici et al.,
2021), reader to retriever knowledge distillation (Izacard and Grave, 2021a),
memory-efficient pipeline (Izacard et al., 2020; Del Tredici et al., 2022),
and leveraging structured information (Min et al., 2019; Yu et al., 2022).
Unlike the Open Domain Question Answering (ODQA) setting, a reassessment of
the baselines in terms of both efficiency and effectiveness appears to be
under-explored in the conversational (ODConvQA) domain. In this paper, we
focus on the typical DPR retriever and FiD reader (DPR+FiD) pipeline, and show
its limitations when applied to the ODConvQA setting. Despite its popularity,
we find that this baseline significantly underperforms when finetuned on
downstream tasks. We show that simple improvements in the training,
architecture, and inference setups of the DPR+FiD pipeline, provide a strong
and efficient baseline that exceeds the performance of SotA models on two
common ODConvQA datasets: TopiOCQA (Adlakha et al., 2022) and ORConvQA (OR-
QuAC) (Qu et al., 2020).
We point out several limitations of the pipeline, such as: 1) reader’s
susceptibility to noisy input, 2) retriever’s reduced coverage, 3) retriever’s
lack of cross semantic encoding between the conversation and the retrieved
passages, and 4) reader’s latency is heavily impacted by the number of input
passages. To mitigate these, we propose and evaluate a simple and effective
approach by including a fast reranking component between the retriever and the
reader, and by performing targeted finetuning steps. The proposed Retriever-
Reranker-Reader finetuning (R3FINE) strategy leads to baseline models with a
better latency/performance trade-off. These baselines, which are simple and
easy to replicate, serve as a reference point for comparing new and more
complex models, and determining their effectiveness. Our contributions are the
following:

  * •

We identify and address several limitations of the typical pipeline used in
ODConvQA.

  * •

We propose the R3FINE strategy, which improves SotA results on two common
datasets and reduces pipeline’s latency by 60%.

  * •

We provide new and valuable insights for creating simple and efficient
baselines, which serve as a reference point for future comparison of new more
complex approaches.

##  2 End-to-End Baselines for ODConvQA

This section provides a brief introduction to the pipeline on which this work
focuses. Figure 1 shows the typical pipeline used within the ODConvQA setting,
featuring an additional reranker component. A conversation history is input to
the DPR retriever. This module exploits a dual-encoder based on the BERT
(Devlin et al., 2019) model. First, it encodes the conversation history via
the $ConversationEncoder$ component, which takes as input the text of the
conversation history $c_{1},c_{2},\dots,c_{i}$, and then it outputs a dense
representation $h_{c}$. Next, this representation is used to perform a dense
search to retrieve the most relevant passages, i.e., text blocks that serve as
basic retrieval units, from an external knowledge source (e.g., Wikipedia).
The latter contains dense representations of the passages that have been
encoded via the $PassageEncoder$ component, which takes as input a $j$-th
passage with a given text length $N$, i.e.,
$p_{j_{1}},p_{j_{2}},\dots,p_{j_{N}}$, and outputs a dense representation
$h_{p_{j}}$. The dense search is performed via the Maximum Inner-Product
Search (MIPS) function which outputs the value corresponding to
$h_{c}^{\intercal}\cdot h_{p_{j}}$.
Once the top-$k$ relevant passages have been retrieved, their text is appended
to the conversation history and subsequently passed to the FiD reader, which
is based on the T5 (Raffel et al., 2020) model. The newly created textual
sequences of length $S$ are then encoded in parallel via the $Encoder$
component that outputs a dense representation
$\bar{h}=\\{h_{1},\dots,h_{S}\\}$. As a final step, the dense representations
of the entire list of $k$ input passages are concatenated to form a single
$\bar{h}_{1}\oplus\bar{h}_{2},\dots,\oplus\bar{h}_{k}$ sequence that forms the
input to the $Decoder$ component responsible for generating the answer $a$.

##  3 Strong Baseline Models

This work focuses on two main datasets. TopiOCQA (Adlakha et al., 2022) is a
large-scale open-domain information-seeking conversational dataset that
contains a challenging phenomenon in the form of topic switching. OR-QuAC (Qu
et al., 2020) leverages CANARD’s (Elgohary et al., 2019) context-independent
question rewrites of the QuAC (Choi et al., 2018) dataset, and adapts it to
the open-domain setting. Further details regarding the datasets are provided
in Appendix A.
We outline a number of limitations of the typical DPR+FiD pipeline, along with
suggestions on how to mitigate them. While some of those interconnect at
different levels the various efforts made in the ODQA domain (Balachandran et
al., 2021; Yu et al., 2022), our goal is to offer a perspective on the
ODConvQA setting.

###  3.1 Current Limitations and Bottlenecks

#### Reader’s susceptibility to noisy input.

Previous findings have shown that the FiD reader performance significantly
improves when increasing the number of retrieved passages (Izacard and Grave,
2021b). While confirming this finding, in Table 1 we also present a different
perspective to it. We show that when the same reader model is provided with
the relevant (i.e., gold) passage in input, the performance decreases as the
number of retrieved passages increases. This suggests that there is a balance
in presenting input to the reader: if the gold passage is present, i.e., the
retriever could retrieve it, a small relevant list is best, but otherwise a
larger list is better.

TopiOCQA
---
| w/o gold | w/ gold
top-$k$ | EM | F1 | EM | F1
1 | 19.3 | 37.6 | 38.3 | 65.5
10 | 29.8 | 52.4 | 35.8 | 61.5
50 | 33.0 | 55.1 | 35.9 | 59.5
Table 1: FiD reader performance (Exact Match and F1 scores) on the TopiOCQA
dev split, with/without the gold passage (w/o gold) in the top-$k$ limit.

#### Retriever’s reduced coverage.

Current solutions impose a hard top-$k$ limit on the number of passages
returned by the DPR retriever and assume that the relevant ones are present
within this limit. Table 1 shows that coverage is key during the retrieval
phase for the reader to perform well. To improve it, we suggest introducing a
simple and efficient Transformer-based (Vaswani et al., 2017) reranker
component after the retriever. This component, shown in Figure 1 and described
in the next paragraph, is designed to reconsider a larger pool of passages
returned by the DPR and to provide the FiD with a reduced and improved list of
passages. Since this module operates at the semantic level, we refer to it as
the $SemanticReranker$. Table 2 shows the potential coverage margins and the
retrieval results obtained after the introduction of such a module, when a
larger number of passages (50 vs 1000) is considered.

#### Retriever’s lack of cross semantic encoding between the conversation and
the retrieved passages.

The DPR retriever performs independent encoding of the passages via the
$PassageEncoder$ function. This means that it is not able to exploit the
semantic relationship among them. This can be mitigated via the introduction
of the previously mentioned $SemanticReranker$ component. This new module is
based on the TransformerEncoder and applies the following function:

$\tilde{h}_{c},\tilde{h}_{p_{1}},\dots,\tilde{h}_{p_{k}}=\\\
Reranker(h_{c},h_{p_{1}},\dots,h_{p_{k}})$

where each element of the input attends to both the conversation dense
representation $h_{c}$ and passages dense representations $h_{p_{i}}$.
Reranking is performed over the new output sequence
$\tilde{h}_{c},\tilde{h}_{p_{1}},\dots,\tilde{h}_{p_{k}}$ via the previously
mentioned MIPS function.

#### Reader’s latency is heavily impacted by the number of input passages.

Figure 2 shows that the latency of the reader can be significantly reduced by
decreasing the number of input passages. However, a trivial limitation to
top-$k$ considerably degrades the performance of the module, thus leading to
an inevitable trade-off. The task of the $SemanticReranker$ involves pushing
relevant passages into the top-$k$ list, and allowing for a low $k$ value to
be set.

| TopiOCQA | OR-QuAC
---|---|---
top-$k$ | w/o SR | w/ SR | w/o SR | w/ SR
1 | 24.66 | 42.64 | 29.27 | 56.64
10 | 62.45 | 75.62 | 57.14 | 72.27
50 | 77.41 | 84.69 | 65.22 | 73.53
1000 | 91.49 | 91.49 | 74.55 | 74.55
Table 2: Dev split retrieval coverage before/after the introduction of the $SemanticReranker$ (w/o SR) when a larger number of passages is considered (50 vs 1000). Figure 2: FiD reader performance (F1 score and latency) on the TopiOCQA dev split and OR-QuAC test split, with varying top-$k$ input passages. Latency is relative to the top-$50$ (top-$k$ vs top-$50$). | TopiOCQA | OR-QuAC
---|---|---
| w/o SR | w/ SR | w/ SR + FT | w/o SR | w/ SR | w/ SR + FT
top-$k$ | EM | F1 | EM | F1 | EM | F1 | EM | F1 | EM | F1 | EM | F1
1 | 19.3 | 37.6 | 28.1 | 50.4 | 30.7 | 52.4 | 14.7 | 23.0 | 13.9 | 25.7 | 16.6 | 28.9
10 | 29.8 | 52.4 | 33.2 | 57.3 | 35.8 | 59.0 | 19.0 | 28.2 | 19.4 | 30.0 | 21.6 | 32.9
50 | 33.0 | 55.1 | 33.9 | 56.2 | 35.2 | 56.1 | 22.0 | 29.9 | 22.1 | 30.2 | 23.5 | 32.2
Table 3: FiD reader performance (Exact Match and F1 scores) on the TopiOCQA
dev split and OR-QuAC test split before/after the introduction of the
$SemanticReranker$ (w/o SR), together with the results obtained after a
further reader finetuning step with top-$10$ output by the SR (w/ SR + FT).
Underlined values indicate the results obtained by the DPR+FiD pipeline. Bold
values indicate the results obtained after the introduction of the SR together
with targeted finetuning steps. TopiOCQA
---
Model | EM | F1
BM25 + DPR Reader | 13.6 | 25.0
BM25 + FiD | 24.1 | 37.2
DPR Retriever + DPR Reader | 21.0 | 43.4
DPR Retriever + FiD | 33.0 | 55.3
(Ours) DPR Retriever + FiD | 33.0 | 55.1
\+ R3FINE (top-$10$) | 35.8 | 59.0
Table 4: TopiOCQA dev split baselines performance (Exact Match and F1 scores)
comparison between sparse/dense retrievers (BM25/DPR Retriever) and
extractive/generative readers (DPR Reader/FiD).

###  3.2 A Strong and Efficient Baseline

Based on the findings above, we introduce the Retriever-Reranker-Reader
finetuning (R3FINE) strategy, which can be used to design strong and efficient
baselines for ODConvQA. First, we increase the number of passages returned by
the DPR from the initial 50 to 1000. Then, we add the $SemanticReranker$
component, which corresponds to a single $TransformerEncoder$ layer. We
train/finetune the $SemanticReranker$ along with the $ConversationEncoder$
while keeping the $PassageEncoder$ frozen. Guided by the intuition that less
but more relevant passages are beneficial to FiD as reported in Table 1, we
finally perform an additional finetuning step by leveraging the new top-$10$
list of passages returned by the $SemanticReranker$.

##  4 Experiments and Results

This section shows the impact that the introduction of the $SemanticReranker$
module has on the pipeline, as well as the finetuning steps we followed to
make the pipeline more efficient without compromising its performance.

#### Experimental Setup.

As the starting point of our experiments, we used the DPR and FiD models
provided with the TopiOCQA dataset. Currently, only the train and dev splits
are made available for this dataset. We followed the same experimental setup
and exploited TopiOCQA’s DPR module for both datasets. Unlike TopiOCQA, OR-
QuAC is of extractive type, and for this reason we trained the FiD module from
scratch by following the same training configuration of TopiOCQA.

OR-QuAC
---
Model | EM | F1
DrQA (Chen et al., 2017) | - | 6.3
BERTserini (Yang et al., 2019) | - | 26.0
ORConvQA (Qu et al., 2020) | - | 29.4
(Ours) DPR Retriever + FiD | 22.0 | 29.9
\+ R3FINE (top-$10$) | 21.6 | 32.9
Table 5: OR-QuAC test split baselines performance (Exact Match and F1 scores)
comparison.

#### End-to-End Results.

Table 4 and Table 5 compare our R3FINE strategy with previous baselines.
R3FINE achieves an F1 score of 59 points on TopiOCQA, and 32.9 on OR-QuAC,
which are 3.9 and 3 points higher than the best models proposed in the
original papers. It is worth noting that these large improvements are achieved
with simple adjustments in the training, architecture, and inference setups of
the well-established DPR+FiD baseline, and not via the introduction of new
heavier and complex models.
To further support our R3FINE strategy, in Table 3 we present an ablation
study which quantifies its impact on the DPR+FiD pipeline. We note that
introducing the $SemanticReranker$ (w/ SR) always outperforms the DPR+FiD
baseline (w/o SR), and at the same time it allows for a 5-fold input size
reduction (top-$10$) while obtaining on-par or better results. In addition, a
further finetuning step of the FiD (w/ SR + FT) outperforms the results
obtained by the $SemanticReranker$ (w/ SR) by 1.7 and 2.9 F1 points on
TopiOCQA and OR-QuAC, respectively. Further experiments and ablation studies
are provided in Appendix A.
Finally, in Figure 2 it can also be observed that using top-$10$ instead of
top-$50$ can reduce FiD’s latency by 60% on average across the two datasets.
We conducted a latency measurement to evaluate the impact of the
$SemanticReranker$ and its associated parameters, with detailed information
available in Appendix A. Given that the $SemanticReranker$ consists of a
single $TransformerEncoder$ layer, its parameters are negligible when compared
to both the DPR and FiD. Moreover, the $SemanticReranker$ accounts only for
0.34% of the overall latency of the FiD reader, adding an additional 2.4ms per
example on top of the 710ms taken by FiD. It is important to note that this
impact is only considered in relation to FiD, as the retrieval phase remains
constant regardless of the inclusion of the $SemanticReranker$.

##  5 Conclusions

In this paper, we identified several limitations of the typical Depnse Passage
Retrieval (DPR) retriever and Fusion-in-Decoder (FiD) reader pipeline when
applied in an ODConvQA setting. We proposed and evaluated an improved approach
by including a fast reranking component between these two modules and by
performing targeted finetuning steps. The proposed R3FINE strategy lead to a
better latency/performance trade-off. The new baseline has proven to be both
strong and efficient when compared to previous baselines, thus making it
suitable for future comparisons of new approaches.

## Limitations

The study presented in this work aimed to identify and address various
limitations of the commonly used ODConvQA pipeline. While our approach may not
be technically groundbreaking, the work’s novelty lies in the presented
findings to design strong and efficient baselines for ODConvQA. It should be
noted that further research is needed to compare the performance of the
proposed R3FINE strategy with other rerankers on non-conversational QA
datasets, which would provide valuable insights into how effective the R3FINE
approach is in different contexts.

## References

  * Adlakha et al. (2022) Vaibhav Adlakha, Shehzaad Dhuliawala, Kaheer Suleman, Harm de Vries, and Siva Reddy. 2022.  TopiOCQA: Open-domain conversational question answering with topic switching.  _Transactions of the Association for Computational Linguistics_ , 10:468–483.
  * Balachandran et al. (2021) Vidhisha Balachandran, Ashish Vaswani, Yulia Tsvetkov, and Niki Parmar. 2021.  Simple and efficient ways to improve REALM.  In _Proceedings of the 3rd Workshop on Machine Reading for Question Answering_ , pages 158–164, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Barlacchi et al. (2022) Gianni Barlacchi, Ivano Lauriola, Alessandro Moschitti, Marco Del Tredici, Xiaoyu Shen, Thuy Vu, Bill Byrne, and Adrià de Gispert. 2022.  Focusqa: Open-domain question answering with a context in focus.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 5195–5208.
  * Chen et al. (2017) Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. 2017.  Reading wikipedia to answer open-domain questions.  In _ACL_.
  * Choi et al. (2018) Eunsol Choi, He He, Mohit Iyyer, Mark Yatskar, Wen-tau Yih, Yejin Choi, Percy Liang, and Luke Zettlemoyer. 2018.  QuAC: Question answering in context.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2174–2184, Brussels, Belgium. Association for Computational Linguistics.
  * Del Tredici et al. (2021) Marco Del Tredici, Gianni Barlacchi, Xiaoyu Shen, Weiwei Cheng, and Adrià de Gispert. 2021.  Question rewriting for open-domain conversational qa: Best practices and limitations.  In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, pages 2974–2978.
  * Del Tredici et al. (2022) Marco Del Tredici, Xiaoyu Shen, Gianni Barlacchi, Bill Byrne, and Adrià de Gispert. 2022.  From rewriting to remembering: Common ground for conversational qa models.  _arXiv preprint arXiv:2204.03930_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  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 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Elgohary et al. (2019) Ahmed Elgohary, Denis Peskov, and Jordan Boyd-Graber. 2019.  Can you unpack that? learning to rewrite questions-in-context.  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 5918–5924, Hong Kong, China. Association for Computational Linguistics.
  * Glass et al. (2022) Michael Glass, Gaetano Rossiello, Md Faisal Mahbub Chowdhury, Ankita Naik, Pengshan Cai, and Alfio Gliozzo. 2022.  Re2G: Retrieve, rerank, generate.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2701–2715, Seattle, United States. Association for Computational Linguistics.
  * Guu et al. (2020) Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang. 2020.  Retrieval augmented language model pre-training.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 3929–3938. PMLR.
  * Hu et al. (2019) Minghao Hu, Yuxing Peng, Zhen Huang, and Dongsheng Li. 2019.  Retrieve, read, rerank: Towards end-to-end multi-document reading comprehension.  In _ACL_.
  * Iyer et al. (2021) Srinivasan Iyer, Sewon Min, Yashar Mehdad, and Wen-tau Yih. 2021.  RECONSIDER: Improved re-ranking using span-focused cross-attention for open domain question answering.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1280–1287, Online. Association for Computational Linguistics.
  * Izacard and Grave (2021a) Gautier Izacard and Edouard Grave. 2021a.  Distilling knowledge from reader to retriever for question answering.  In _International Conference on Learning Representations_.
  * Izacard and Grave (2021b) Gautier Izacard and Edouard Grave. 2021b.  Leveraging passage retrieval with generative models for open domain question answering.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 874–880, Online. Association for Computational Linguistics.
  * Izacard et al. (2020) Gautier Izacard, Fabio Petroni, Lucas Hosseini, Nicola De Cao, Sebastian Riedel, and Edouard Grave. 2020.  A memory efficient baseline for open domain question answering.  _ArXiv_ , abs/2012.15156.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020.  Dense passage retrieval for open-domain question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6769–6781, Online. Association for Computational Linguistics.
  * Lee et al. (2019) Kenton Lee, Ming-Wei Chang, and Kristina Toutanova. 2019.  Latent retrieval for weakly supervised open domain question answering.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6086–6096, Florence, Italy. Association for Computational Linguistics.
  * Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 9459–9474. Curran Associates, Inc.
  * Mao et al. (2021) Yuning Mao, Pengcheng He, Xiaodong Liu, Yelong Shen, Jianfeng Gao, Jiawei Han, and Weizhu Chen. 2021.  Reader-guided passage reranking for open-domain question answering.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 344–350, Online. Association for Computational Linguistics.
  * McCallum et al. (2019) Andrew McCallum, Manzil Zaheer, Rajarshi Das, and Shehzaad Dhuliawala. 2019.  Multi-step retriever-reader interaction for scalable open-domain question answering.  In _ICLR_.
  * Min et al. (2019) Sewon Min, Danqi Chen, Luke Zettlemoyer, and Hannaneh Hajishirzi. 2019.  Knowledge guided text retrieval and reading for open domain question answering.  _ArXiv_ , abs/1911.03868.
  * Oddy (1977) Robert N. Oddy. 1977.  Information retrieval through man-machine dialogue.  _Journal of Documentation_ , 33:1–14.
  * Qu et al. (2020) Chen Qu, Liu Yang, Cen-Chieh Chen, Minghui Qiu, W. Bruce Croft, and Mohit Iyyer. 2020.  Open-retrieval conversational question answering.  _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_.
  * Qu et al. (2021) Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. 2021.  RocketQA: An optimized training approach to dense passage retrieval for open-domain question answering.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5835–5847, Online. Association for Computational Linguistics.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Shen et al. (2023) Xiaoyu Shen, Svitlana Vakulenko, Marco Del Tredici, Gianni Barlacchi, Bill Byrne, and Adrià de Gispert. 2023.  Neural ranking with weak supervision for open-domain question answering: A survey.  In _Findings of the Association for Computational Linguistics: EACL 2023_ , pages 1691–1705.
  * Vakulenko et al. (2021) Svitlana Vakulenko, Shayne Longpre, Zhucheng Tu, and Raviteja Anantha. 2021.  Question rewriting for conversational question answering.  In _Proceedings of the 14th ACM international conference on web search and data mining_ , pages 355–363.
  * Vaswani et al. (2017) Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _NIPS_.
  * Yang et al. (2019) Wei Yang, Yuqing Xie, Aileen Lin, Xingyu Li, Luchen Tan, Kun Xiong, Ming Li, and Jimmy J. Lin. 2019.  End-to-end open-domain question answering with bertserini.  In _NAACL_.
  * Yu et al. (2022) Donghan Yu, Chenguang Zhu, Yuwei Fang, Wenhao Yu, Shuohang Wang, Yichong Xu, Xiang Ren, Yiming Yang, and Michael Zeng. 2022.  KG-FiD: Infusing knowledge graph in fusion-in-decoder for open-domain question answering.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 4961–4974, Dublin, Ireland. Association for Computational Linguistics.

##  Appendix A Appendix

This section provides additional information in support of the work done
within the paper.

###  A.1 OR-QuAC conversion to TopiOCQA’s format and models

To make the OR-QuAC dataset compatible with TopiOCQA’s models, we applied the
following steps:

  * •

all answers of type CANNOTANSWER and NOTRECOVERED have been mapped to
UNANSWERABLE

  * •

for the DPR’s $ConversationEncoder$ component, we followed the TopiOCQA’s
AllHistory conversation representation

  * •

for the DPR’s $PassageEncoder$ component, each passage title has been reduced
from "passage_page_title [SEP] passage_page_subtitle" to "passage_page_title".
This is due to the fact that, compared to TopiOCQA, OR-QuAC does not provide
the information about the section where a particular passage is located within
the page.

  * •

for the FiD component, each passage information has been reduced from "title:
sub-title: context:" to "title: context:". This is done for the same reason
mentioned in the previous point.

Each passage text in OR-QuAC’s Wikipedia knowledge source has been mapped to
its corresponding embedding via the TopiOCQA’s $PassageEncoder$ component. We
then performed the same retrieval step as the one done for TopiOCQA. We
exploited TopiOCQA’s DPR module for both datasets as the retrieval phase is
very similar between the two. However, given that, unlike TopiOCQA, OR-QuAC is
of extractive type, we had to train the FiD module from scratch. We followed
the same training configuration as the one used for TopiOCQA.

$L$ | $h_{c_{1}}$ | $h_{c_{1}},\dots,h_{c_{i}}$ | $p_{1},\dots,p_{k}$ | $CrossEncoder$ | TopiOCQA | OR-QuAC
---|---|---|---|---|---|---
1 | ✓ |  | ✓ | ✓ | 78.85 | 71.51
1 |  | ✓ | ✓ | ✓ | 78.88 | 71.48
4 |  | ✓ | ✓ | ✓ | 78.84 | 71.32
1 | ✓ |  | ✓ |  | 77.17 | 69.83
1 |  | ✓ | ✓ |  | 77.35 | 70.18
4 |  | ✓ | ✓ |  | 77.30 | 70.45
1 |  |  | ✓ |  | 67.07 | 64.18
Table 6: Average top-$k$ results obtained on the TopiOCQA and OR-QuAC dev
split, with different configurations.

###  A.2 Reranker training and ablation study

We tried different configurations of the $SemanticReranker$ to find the most
efficient and effective one. In addition to the decision of whether to
finetune the DPR’s $ConversationEncoder$ together with the $SemanticReranker$,
we also tried varying the number of layers $L$ of the $SemanticReranker$ from
1 to 4 and changing its input, by choosing a combination from:

  * •

$h_{c_{1}}$: use of conversation’s history dense representation

  * •

$h_{c_{1}},\dots,h_{c_{i}}$: use of conversation’s history tokens dense
representation

  * •

$p_{1},\dots,p_{k}$: use of passages dense representation

Table 6 shows the average top-$k$ results obtained on the TopiOCQA and OR-QuAC
dev split, where $k$ varies between 1, 3, 5, 10, 15, 20, 30, 50, 100, 250,
500, 750, and 1000. For TopiOCQA, we report the presence of the gold passage
within the top-$k$ limit. For OR-QuAC we report the presence of the gold
answer within the top-$k$ limit.
Given that the MIPS function cannot be applied when $p_{1},\dots,p_{k}$
representations are used alone, i.e, without the conversation history, we
applied a linear projection on top of the $SemanticReranker$ to obtain a score
for each passage in input.
As far as training the $SemanticReranker$ is concerned, we trained it for 10
epochs when finetuned together with the $ConversationEncoder$. We instead
trained it for 20 epochs when the $ConversationEncoder$ was kept frozen and
when $p_{1},\dots,p_{k}$ representations were used alone. We leveraged the
same objective function used for training the initial DPR. We used early
stopping to chose the best performing model on the dev set. We also used a
linear learning rate decay throughout the training process, and AdamW with a
learning rate of 5e-5 and weight decay of 1e-2.
Among the different combinations shown in Table 6, we considered the first
entry as the best choice, i.e., the model with $L=1$, $h_{c_{1}}$,
$p_{1},\dots,p_{k}$, and $CrossEncoder$ finetuning.

###  A.3 Retriever results

Table 7 shows the train split retrieval coverage before/after the introduction
of the $SemanticReranker$ (w/o SR) when a larger number of passages is
considered (50 vs 1000). For both datasets, we report the presence of the gold
passage within the top-$k$ limit.

| TopiOCQA | OR-QuAC
---|---|---
top-$k$ | w/o SR | w/ SR | w/o SR | w/ SR
1 | 31.54 | 98.25 | 31.69 | 77.31
5 | 66.99 | 99.71 | 59.08 | 89.10
10 | 78.29 | 99.72 | 66.31 | 89.36
20 | 86.78 | 99.72 | 71.77 | 89.40
50 | 93.55 | 99.72 | 77.35 | 89.40
500 | 99.36 | 99.72 | 87.15 | 89.41
1000 | 99.72 | 99.72 | 89.41 | 89.41
Table 7: Train split retrieval coverage before/after the introduction of the $SemanticReranker$ (w/o SR) when a larger number of passages is considered (50 vs 1000). For both datasets, we report the presence of the gold passage within the top-$k$ limit. | TopiOCQA | OR-QuAC
---|---|---
top-$k$ | w/o SR | w/ SR | w/o SR | w/ SR
1 | 24.66 | 42.64 | 29.27 | 56.64
5 | 51.87 | 68.62 | 51.63 | 70.82
10 | 62.45 | 75.62 | 57.14 | 72.27
20 | 70.21 | 80.75 | 61.37 | 72.80
50 | 77.41 | 84.69 | 65.22 | 73.53
500 | 89.58 | 90.73 | 72.97 | 74.34
1000 | 91.49 | 91.49 | 74.55 | 74.55
Table 8: Dev split retrieval coverage before/after the introduction of the
$SemanticReranker$ (w/o SR) when a larger number of passages is considered (50
vs 1000). For TopiOCQA, we report the presence of the gold passage within the
top-$k$ limit. For OR-QuAC we report the presence of the gold answer within
the top-$k$ limit.

Table 8 shows the dev split retrieval coverage before/after the introduction
of the $SemanticReranker$ (w/o SR) when a larger number of passages is
considered (50 vs 1000). For TopiOCQA, we report the presence of the gold
passage within the top-$k$ limit. For OR-QuAC we report the presence of the
gold answer within the top-$k$ limit. Table 9 shows the OR-QuAC test split
retrieval coverage before/after the introduction of the $SemanticReranker$
(w/o SR) when a larger number of passages is considered (50 vs 1000). We
report the presence of the gold answer within the top-$k$ limit.

| OR-QuAC
---|---
top-$k$ | w/o SR | w/ SR
1 | 26.82 | 48.75
5 | 46.29 | 64.71
10 | 51.50 | 66.47
20 | 55.63 | 67.31
50 | 59.85 | 68.10
500 | 67.87 | 69.48
1000 | 69.86 | 69.86
Table 9: OR-QuAC test split retrieval coverage before/after the introduction
of the $SemanticReranker$ (w/o SR) when a larger number of passages is
considered (50 vs 1000). We report the presence of the gold answer within the
top-$k$ limit.

###  A.4 Reader results

Table 10, Table 11, and Table 12 show the impact the introduction of the
$SemanticReranker$ has on the FiD reader. The input to the FiD reader are
either passages returned by the initial DPR retriever (w/o SR) or passages
returned by the $SemanticReranker$ (w/ SR).

TopiOCQA
---
| w/o SR | w/ SR
top-$k$ | EM | F1 | EM | F1
1 | 19.3 | 37.6 | 28.1 | 50.4
5 | 27.0 | 49.6 | 32.2 | 56.5
10 | 29.8 | 52.4 | 33.2 | 57.3
20 | 31.3 | 54.0 | 33.4 | 56.5
50 | 33.0 | 55.1 | 33.9 | 56.2
Table 10: FiD reader performance (Exact Match and F1 scores) on the TopiOCQA
dev split before/after the introduction of the $SemanticReranker$ (w/o SR).
OR-QuAC
---
| w/o SR | w/ SR
top-$k$ | EM | F1 | EM | F1
1 | 13.2 | 22.2 | 12.2 | 25.9
5 | 16.4 | 26.3 | 16.4 | 28.7
10 | 18.0 | 27.6 | 18.0 | 29.4
20 | 19.2 | 28.2 | 18.9 | 29.2
50 | 19.6 | 27.7 | 19.3 | 27.7
Table 11: FiD reader performance (Exact Match and F1 scores) on the OR-QuAC
dev split before/after the introduction of the $SemanticReranker$ (w/o SR).
OR-QuAC
---
| w/o SR | w/ SR
top-$k$ | EM | F1 | EM | F1
1 | 14.7 | 23.0 | 13.9 | 25.7
5 | 17.8 | 27.1 | 17.9 | 29.5
10 | 19.0 | 28.2 | 19.4 | 30.0
20 | 20.3 | 29.1 | 20.8 | 30.5
50 | 22.0 | 29.9 | 22.1 | 30.2
Table 12: FiD reader performance (Exact Match and F1 scores) on the OR-QuAC
test split before/after the introduction of the $SemanticReranker$ (w/o SR).

###  A.5 Reader is susceptible to noisy input

Table 13 shows the FiD reader performance on the TopiOCQA dev split,
with/without the gold passage (w/o gold) in the top-$k$ limit. This analysis
is limited to the TopiOCQA dataset as it is the only one to provide
information about the gold passage for the dev split.

TopiOCQA
---
| w/o gold | w/ gold
top-$k$ | EM | F1 | EM | F1
1 | 19.3 | 37.6 | 38.3 | 65.5
5 | 27.0 | 49.6 | 36.3 | 62.5
10 | 29.8 | 52.4 | 35.8 | 61.5
20 | 31.3 | 54.0 | 36.2 | 60.8
50 | 33.0 | 55.1 | 35.9 | 59.5
Table 13: FiD reader performance (Exact Match and F1 scores) on the TopiOCQA
dev split, with/without the gold passage (w/o gold) in the top-$k$ limit.

###  A.6 Further reader study

To better understand the impact that the introduction of the
$SemanticReranker$ has on the FiD reader, Table 14, Table 15, and Table 16
show the results obtained after taking a non-finetuned FiD and training it on
the top-$10$ passages returned by the initial DPR retriever and on the
top-$10$ passages returned by the $SemanticReranker$. On both datasets, we
followed the same training configuration as the one used for TopiOCQA.

TopiOCQA
---
| w/o SR | w/ SR
top-$k$ | EM | F1 | EM | F1
1 | 19.2 | 37.8 | 29.5 | 50.9
5 | 27.8 | 49.9 | 34.0 | 56.9
10 | 30.4 | 52.0 | 34.3 | 57.0
Table 14: FiD reader performance (Exact Match and F1 scores) on the TopiOCQA
dev split after taking a non-finetuned FiD and training it on the top-$10$
passages returned by the initial DPR retriever (w/o SR) and on the top-$10$
passages returned by the $SemanticReranker$ (w/ SR). OR-QuAC
---
| w/o SR | w/ SR
top-$k$ | EM | F1 | EM | F1
1 | 14.2 | 23.1 | 13.9 | 27.6
5 | 18.0 | 27.7 | 18.1 | 30.8
10 | 19.2 | 28.9 | 19.3 | 31.2
Table 15: FiD reader performance (Exact Match and F1 scores) on the OR-QuAC
dev split after taking a non-finetuned FiD and training it on the top-$10$
returned by the initial DPR retriever (w/o SR) and on the top-$10$ returned by
the $SemanticReranker$ (w/ SR). OR-QuAC
---
| w/o SR | w/ SR
top-$k$ | EM | F1 | EM | F1
1 | 15.5 | 23.9 | 15.8 | 28.3
5 | 19.6 | 29.1 | 19.4 | 31.7
10 | 20.9 | 29.7 | 20.6 | 31.9
Table 16: FiD reader performance (Exact Match and F1 scores) on the OR-QuAC
test split after taking a non-finetuned FiD and training it on the top-$10$
passages returned by the initial DPR retriever (w/o SR) and on the top-$10$
passages returned by the $SemanticReranker$ (w/ SR).

Table 17, Table 18, and Table 19 show instead the results obtained after
taking an already finetuned FiD reader and further finetuning it on the
top-$10$ passages returned by the initial DPR retriever and on the top-$10$
passages returned by the $SemanticReranker$. On both datasets, the amount of
finetuning steps is equal to the one used for training the already finetuned
FiD reader.

TopiOCQA
---
| w/o SR | w/ SR
top-$k$ | EM | F1 | EM | F1
1 | 21.5 | 39.3 | 30.7 | 52.4
5 | 30.4 | 52.3 | 36.1 | 59.4
10 | 32.8 | 54.6 | 35.8 | 59.0
Table 17: FiD reader performance (Exact Match and F1 scores) on the TopiOCQA
dev split after taking an already finetuned FiD and further finetuning it on
the top-$10$ returned by the initial DPR retriever (w/o SR) and on the
top-$10$ returned by the $SemanticReranker$ (w/ SR). OR-QuAC
---
| w/o SR | w/ SR
top-$k$ | EM | F1 | EM | F1
1 | 15.2 | 23.8 | 15.4 | 29.0
5 | 18.9 | 28.4 | 18.4 | 31.2
10 | 19.9 | 29.4 | 20.1 | 32.0
Table 18: FiD reader performance (Exact Match and F1 scores) on the OR-QuAC
dev split after taking an already finetuned FiD and further finetuning it on
the top-$10$ passages returned by the initial DPR retriever (w/o SR) and on
the top-$10$ passages returned by the $SemanticReranker$ (w/ SR). OR-QuAC
---
| w/o SR | w/ SR
top-$k$ | EM | F1 | EM | F1
1 | 16.7 | 24.9 | 16.6 | 28.9
5 | 20.0 | 29.2 | 20.1 | 32.2
10 | 21.4 | 30.0 | 21.6 | 32.9
Table 19: FiD reader performance (Exact Match and F1 scores) on the OR-QuAC
test split after taking an already finetuned FiD and further finetuning it on
the top-$10$ passages returned by the initial DPR retriever (w/o SR) and on
the top-$10$ passages returned by the $SemanticReranker$ (w/ SR).

###  A.7 Latency measurement

Latency measurement (see Figure 2) has been performed on the same NVIDIA V100
16GB GPU, by following the FiD’s test_reader.py script provided with the
TopiOCQA dataset. We set the per_gpu_batch_size paramenter to 4 in all runs
and chose the value of the n_context parameter from 1, 3, 5, 10, 20, 30, and
50, based on the number of input passages. For each value, we report the
latency relative to the maximum n_context parameter value, i.e., 50. We used
CUDA events synchronization markers to measure the elapsed time for the
preprocessing and evaluation of TopiOCQA’s dev split and OR-QuAC’s test split.


# Zero-sum continuous-time Markov games with one-side stopping

Yurii Averboukh

###### Abstract

The paper is concerned with a variant of the continuous-time finite state
Markov game of control and stopping where both players can affect transition
rates, while only one player can choose a stopping time. We use the dynamic
programming principle and reduce this problem to a system of ODEs with
unilateral constraints. This system plays the role of the Bellman equation. We
show that its solution provides the optimal strategies of the players.
Additionally, we prove the existence and uniqueness theorem for the deduced
system of ODEs with unilateral constraints.
MSC Classification (2020): 91A05, 91A25, 90C40, 60G40, 60J27.
Keywords: continuous-time Markov games, dynamic programming, verification
theorem, stopping time.

##  1 Introduction

The continuous-time Markov processes can be controlled in two ways. First, the
decision maker can affect transition rates. The second way involves the choice
of the stopping time. The case where the transition rates are controlled
refers to the Markov decision problem (see [7], [6] and reference therein for
the detailed explanation of this field). The optimization of the Markov chain
by the means of stopping time is studied within the optimal stopping theory
[11, 12]. Certainly, one can mix both ways and study Markov decision processes
with stopping [8]. The concept of Markov chain affected by several decision
makers leads to such settings as the continuous time Markov games those
examine the case when all players control transition rates [14], the Dynkin
games [3, 4] where the players choose stopping times and the games of control
and stopping where all players can affect the transition rates as well as the
stopping time [5]. In the paper, we consider one-side stopping Markov game
that implies that one player chooses a control and a stopping time, while the
other one affects only the control. Our interest to this problem is motivated
by the possible application of these games to the differential games with
minimal cost studied in [2, 13]. In particular, it is shown that one can find
a one-side stopping Markov game such that its value function approximates the
value function of the original differential game with minimal cost [1].

We study the continuous-time finite state Markov chain governed by two
decision makers with opposite purposes. Without loss of generality, we assume
that the state space is $\mathcal{S}=\\{1,\ldots,d\\}$. The transition rates
are described by the Kolmogorov matrix
$Q(t,u,v)=(Q_{i,j}(t,u,v))_{i,j=1}^{d}$, i.e., for each $t$, $u$ and $v$,

$Q_{i,j}(t,u,v)\geq 0\text{ for }i\neq j,$

while

$\sum_{j\in\mathcal{S}}Q_{i,j}=0.$

Here $u$ (respectively, $v$) is a control of the first (respectively, second)
player. It is assumed that $u\in U$, $v\in V$, while $t\in[0,T]$. We assume
that the stopping of the game is chosen by the first player. If $t_{0}$ is an
initial time, $X(t)$ is a state of the Markov chain at time $t$, while $\tau$
is a stopping time, then the quality of the examined one-side Markov game is
evaluated by

$g(\tau,X(\tau))+\int_{t_{0}}^{\tau}h(t^{\prime},X(t^{\prime}),u(t^{\prime}),v(t^{\prime}))dt^{\prime}.$
(1)

Here $\mathbb{E}$ stands for the expectation. We assume that the first player
tries to minimize functional (1), while the second player wishes to maximize
it.

The universal tool for the study of Markov decision processes, Markov games as
well as optimal stopping problems is the dynamic programming principle. It
primary relies on the feedback strategies and reduces the problem of design of
optimal strategies to a certain Bellman equation. In the case of the finite
horizon Markov decision processes and the Markov games, the Bellman equation
takes a form of system of ODEs. For the game theoretical case, this system was
derived in paper by Zachrisson [14]. Thus, we call it a Zachrisson equation.

In the paper, we use the dynamic programming principle and show the players’
optimal strategies can be constructed based on the solution of the Zachrisson
equation with unilateral constraints. Thus, the existence result for the one-
side stopping Markov game is reduced to the existence theorem for the
Zachrisson equation with unilateral constraints that is also obtained in the
paper.

The rest of the paper is organized as follows. In Section 2, we formalize the
concept of one-side stopping Markov game and introduce the classes of
strategies. The main results are formulated in Section 3. Here, we, first,
claim that, given a solution of the Zachrisson equation with unilateral
constraints, one can design optimal players’ strategies. Additionally, in this
section, we formulate the existence and uniqueness result for the Zachrisson
equation with unilateral constraints. These statements imply the existence of
the value function of the examined one-side stopping Markov game. Section 4 is
concerned with the proof of the first result by the verification argument. The
proof of the existence and uniqueness theorem for the Zachrisson equation with
unilateral constraints is given in Section 5.

##  2 Preliminaries

In the paper, we identify every function
$\phi:\mathcal{S}\rightarrow\mathbb{R}$ with the corresponding vector in
$\mathbb{R}^{d}$ and assume that $\phi(i)$ and $\phi_{i}$ have the same
meaning.

Given an initial time $t_{0}$, we fix the measurable space
$(\Omega_{t_{0}},\mathcal{F}_{t_{0}})$ letting $\Omega_{t_{0}}$ to be equal to
the space of càdlàg functions from $[t_{0},T]$ to $\mathcal{S}$ and choosing
$\mathcal{F}_{t_{0}}$ to be a Borel $\sigma$-algebra on $\Omega_{t_{0}}$,
i.e., $\Omega_{t_{0}}\triangleq D([t_{0},T],\mathcal{S})$, and
$\mathcal{F}_{t_{0}}\triangleq\mathcal{B}(D([t_{0},T],\mathcal{S}))$.

If $s,r\in[t_{0},T]$, $s<r$, then denote by $\mathcal{R}^{s,r}$ operator
assigning to $\omega\in\Omega_{t_{0}}=D([t_{0},T],\mathcal{S})$ its
restriction on $[s,r]$.

Further, we put $\mathcal{F}_{t_{0},t}$ to be the $\sigma$-algebra of sets
$A\in\Omega_{t_{0}}$ such that
$\mathcal{R}^{t_{0},t}(A)\in\mathcal{B}(D([t_{0},t],\mathcal{S}))$ and
$\mathcal{R}^{t,T}(A)\in\\{\varnothing,D([t,T],\mathcal{S})\\}$. Obviously,
$\mathbb{F}_{t_{0}}\triangleq\\{\mathcal{F}_{t_{0},t}\\}_{t\in[t_{0},T]}$ is a
filtration on $\mathcal{F}_{t_{0}}$. We denote the set of stopping time w.r.t.
the filtration $\mathbb{F}_{t_{0}}$ taking values in $[t_{0},T]$ by
$\mathcal{T}_{t_{0}}$.

If $\phi:[0,T]\times\mathcal{S}\rightarrow\mathbb{R}$ is differentiable at
$s\in[0,T]$ for some $i\in\mathcal{S}$, and $\omega\in\Omega_{t_{0}}$ is such
that $\omega(s)=i$, we use the notation

$\frac{\partial}{\partial t}\phi(s,\omega(s))$

for the derivative of the function $\phi$ w.r.t. the time variable at the
point $s$, $i=\omega(s)$.

Below, we denote by $\mathcal{AC}$ the set of all functions
$\phi:[0,T]\times\mathcal{S}\rightarrow\mathbb{R}$ such that mapping
$t\mapsto\phi(t,i)$ is absolutely continuous for each $i\in\mathcal{S}$.

We consider two types of strategies. First, we will assume that the player has
information only about current state and time. This leads to the concept of
feedback strategies.

######  Definition 2.1.

A measurable w.r.t. the time mapping $u$ from $[0,T]\times\mathcal{S}$ to $U$
is called a first player’s feedback strategy.

We denote the set of all feedback strategies of the first player by
$\mathcal{U}_{\operatorname{fb}}$. As it was mentioned above the first player
also chooses the stopping time. Within the feedback approach, it is controlled
by the stopping rule defined as follows.

######  Definition 2.2.

A cádlág function from $[0,T]\times\mathcal{S}$ to $\\{0,1\\}$ is called a
stopping rule.

We will assume that the game stops at the first time when the stopping rule is
equal to $1$, i.e., if $\vartheta$ is a stopping rule, then the corresponding
stopping time on $[t_{0},T]$ is defined by the rule:

$\bar{\tau}_{t_{0}}[\vartheta](\omega)\triangleq\min\\{t\in[t_{0},T]:\vartheta(t,\omega(t))=1\\}.$

The set all stopping rules is denoted by $\mathcal{T}_{\operatorname{fb}}$.

The feedback strategies of the second player are defined in the same way.

######  Definition 2.3.

We say that a mapping $v:[0,T]\times\mathcal{S}\rightarrow V$ is a second
player’s strategy provided that $v$ is measurable w.r.t. the time variable.

The set of feedback strategies is denoted by
$\mathcal{V}_{\operatorname{fb}}$.

Since we consider the guaranteed results of the players, it is reasonable to
follow the approach of [10] and enlarge of the set of strategies admitting
strategies with memory.

######  Definition 2.4.

If $t_{0}$ is an initial time, a $\mathbb{F}_{t_{0}}$-progressively measurable
process with values in $U$ (respectively, $V$) is called a strategy with
memory of the first (respectively, second) player on $[t_{0},T]$.

We denote the set of strategies with memory of the first (respectively,
second) player on $[t_{0},T]$ by $\mathcal{U}_{t_{0}}$ (respectively,
$\mathcal{V}_{t_{0}}$).

The link between feedback strategies and strategies with memory is
straightforward. If $u\in\mathcal{U}_{\operatorname{fb}}$, then $\alpha[u]$
defined by the rule

$\alpha[u](t,\omega)\triangleq u(t,\omega(t))$

is a strategy with memory. Analogously, given
$v\in\mathcal{V}_{\operatorname{fb}}$, we define the corresponding strategy
with memory $\beta[v]$ setting $\beta[v](t,\omega)\triangleq v(t,\omega(t))$.

The probability on $\mathcal{F}_{t_{0}}$ generated by two strategies, initial
time and initial state is defined in the following way.

######  Definition 2.5.

Given two strategies with memory $\alpha\in\mathcal{U}_{t_{0}}$ and
$\beta\in\mathcal{V}_{t_{0}}$, an initial time $t_{0}\in[0,T]$ and an initial
state $i_{0}\in\mathcal{S}$, we say that the probability
$\mathbb{P}^{\alpha,\beta}_{t_{0},i_{0}}$ on $\mathcal{F}_{t_{0}}$ is
generated by $\alpha$, $\beta$, $t_{0}$ and $i_{0}$ provided that

  * •

$\mathbb{P}_{t_{0},i_{0}}^{\alpha,\beta}(\\{\omega:\omega(t_{0})=i_{0}\\})=1$.

  * •

for every $\phi\in\mathcal{AC}$, the process

$\phi(t,\omega(t))-\int_{t_{0}}^{t}\bigg{[}\frac{\partial}{\partial
t}\phi(t^{\prime},\omega(t^{\prime}))+\sum_{j\in\mathcal{S}}Q_{\omega(t^{\prime}),j}(t^{\prime},\alpha(t^{\prime},\omega),\beta(t^{\prime},\omega))\phi(t^{\prime},j)\bigg{]}dt^{\prime}$
(2)

is $(\mathbb{P}_{t_{0},i_{0}}^{\alpha,\beta},\mathbb{F})$-martingale.

Below $\mathbb{E}_{t_{0},i_{0}}^{\alpha,\beta}$ stands for the expectation
corresponding to the probability $\mathbb{P}_{t_{0},i_{0}}^{\alpha,\beta}$.

If $\alpha=\alpha[u]$ for some feedback strategy of the first player $u$, we
will write $\mathbb{P}_{t_{0},i_{0}}^{u,\beta}$ instead of
$\mathbb{P}_{t_{0},i_{0}}^{\alpha[u],\beta}$. Analogously,
$\mathbb{P}_{t_{0},i_{0}}^{\alpha,v}\triangleq\mathbb{P}_{t_{0},i_{0}}^{\alpha,\beta[v]}$.
Notice that the probability $\mathbb{P}^{u,v}_{t_{0},i_{0}}$ is always well-
defined. Additionally, one can prove that
$\mathbb{P}_{t_{0},i_{0}}^{\alpha,\beta}$ exists in the case when both
$\alpha$ and $\beta$ depend on a finite number of time instants.

The quality of the players’ strategies is evaluated as follows. Given initial
time $t_{0}\in[0,T]$, initial state $i_{0}\in\mathcal{S}$, a first player’s
strategy $\alpha\in\mathcal{U}_{t_{0}}$, a stopping time
$\tau\in\mathcal{T}_{t_{0}}$ and a strategy of the second player
$\beta\in\mathcal{V}_{t_{0}}$, the corresponding payoff within the one-side
stopping Markov game is equal to

$\mathbb{E}_{t_{0},i_{0}}^{\alpha,\beta}G_{t_{0}}^{\alpha,\beta}(\tau),$

where we denote

$G_{t_{0}}^{\alpha,\beta}(t,\omega)\triangleq
g(t,\omega(t))+\int_{t_{0}}^{t}h(t^{\prime},\omega(t^{\prime}),\alpha(t^{\prime},\omega),\beta(t^{\prime},\omega))dt^{\prime}.$

As above, in the case when $\alpha=\alpha[u]$ (respectively,
$\beta=\beta[v]$), we will write $G_{t_{0}}^{u,\beta}$ (respectively,
$G_{t_{0}}^{\alpha,v}$).

##  3 Main result

We impose the following assumptions:

  1. (H1)

The control spaces $U$ and $V$ are compact;

  2. (H2)

the transition rates $Q_{i,j}$ and the payoff functions $g(\cdot,i)$,
$h(\cdot,i,\cdot,\cdot)$ are continuous for each $i$ and $j$;

  3. (H3)

the function $g$ is Lipschitz continuous w.r.t. the time variable;

  4. (H4)

for every $t\in[0,T]$, $i\in\mathcal{S}$ and each $w\in\mathbb{R}^{d}$,

$\begin{split}\min_{u\in U}\max_{v\in
V}\sum_{j\in\mathcal{S}}&{}\Bigl{[}Q_{i,j}(t,u,v)w_{j}+h(t,i,u,v)\Bigr{]}\\\
&=\max_{v\in V}\min_{u\in
U}\sum_{j\in\mathcal{S}}\Bigl{[}Q_{i,j}(t,u,v)w_{j}+h(t,i,u,v)\Bigr{]}.\end{split}$

Notice that assumption (H4) can be considered as an analog of the Isaacs’
condition in the theory of differential games [10].

We consider the upper and lower values of the game those corresponds to the
upper and lower games. We assume that within the upper game the first player
chooses his/her strategy (that includes both controls and stopping time) from
the class of feedback strategies, while the response of the second player is
from the class of strategies with memory. Formally, this means the advantage
of the second player. In the lower game, we give the advantage to the first
player. The second player’s choice is restricted to the class of feedback
strategies, while the first player chooses his/her policy from the class of
strategies with memory.

Therefore, the upper and lower values of the one-side stopping Markov game are
defined by the rules:

$\operatorname{Val}^{+}(t_{0},i_{0})\triangleq\inf_{u\in\mathcal{U}_{\operatorname{fb}}}\inf_{\vartheta\in\mathcal{T}_{\operatorname{fb}}}\sup_{\beta\in\mathcal{V}_{t_{0}}}\mathbb{E}_{t_{0},i_{0}}^{u,\beta}G_{t_{0}}^{u,\beta}(\bar{\tau}_{t_{0}}[\vartheta]),$
$\operatorname{Val}^{-}(t_{0},i_{0})\triangleq\sup_{v\in\mathcal{V}_{\operatorname{fb}}}\inf_{\alpha\in\mathcal{U}_{t_{0}}}\inf_{\tau\in\mathcal{T}_{t_{0}}}\mathbb{E}_{t_{0},i_{0}}^{\alpha,v}G_{t_{0}}^{\alpha,v}(\tau).$

Notice that due to the fact that, for each $t_{0}\in[0,T]$,
$i_{0}\in\mathcal{S}$, $u\in\mathcal{U}_{\operatorname{fb}}$,
$v\in\mathcal{V}_{\operatorname{fb}}$, the probability
$\mathbb{P}^{u,v}_{t_{0},i_{0}}$ is well-defined, we have that all
aforementioned values are finite.

Moreover,

$\operatorname{Val}^{+}(t_{0},i_{0})\geq\operatorname{Val}^{-}(t_{0},i_{0}).$
(3)

Below, we show that the one-side stopping Markov games has a value.
Additionally, we will show that this value can be obtained as a solution of
the Zachrisson equation with unilateral constraints. The latter object is
defined as follows. For $w\in\mathbb{R}^{d}$, $i\in\mathcal{S}$, set

$H_{i}(t,w)\triangleq\min_{u\in U}\max_{v\in
V}\sum_{j\in\mathcal{S}}\Bigl{[}Q_{i,j}(t,u,v)w_{j}+h(t,i,u,v)\Bigr{]}.$ (4)

Notice that, due to assumption (H4),

$H_{i}(t,w)=\max_{v\in V}\min_{u\in
U}\sum_{j\in\mathcal{S}}\Bigl{[}Q_{i,j}(t,u,v)w_{j}+h(t,i,u,v)\Bigr{]}.$

Below, if $\phi:[0,T]\times\mathcal{S}\rightarrow\mathbb{R}$, the $\phi(t)$
stands for the vector $(\phi(t,1),\ldots,\phi(t,d))^{T}$.

######  Definition 3.1.

We say that a function $\varphi\in\mathcal{AC}$ satisfies the Zachrisson
equation with unilateral constraints if, for each $i\in\mathcal{S}$,

  1. (Z1)

$\varphi(T,i)=g(T,i)$;

  2. (Z2)

$\varphi(t,i)\leq g(t,i)$ for $t\in[0,T]$;

  3. (Z3)

for every point $t\in[0,T]$ such that $\frac{d}{dt}\varphi(t,i)$ is well-
defined and $\varphi(t,i)<g(t,i)$, one has

$\frac{d}{dt}\phi(t,i)\leq-H_{i}(t,\varphi(t));$

  4. (Z4)

if $\phi(\cdot,i)$ is differentiable at $t\in[0,T]$, then

$\frac{d}{dt}\phi(t,i)\geq-H_{i}(t,\varphi(t)).$

######  Theorem 3.2.

Let $\varphi$ satisfy the Zachrisson equation with unilateral constraints.
Then at every $t_{0}\in[0,T]$, $i_{0}\in\mathcal{S}$,

$\operatorname{Val}^{+}(t_{0},i_{0})=\operatorname{Val}^{-}(t_{0},i_{0})=\varphi(t_{0},i_{0}).$

######  Theorem 3.3.

There exists a unique function $\varphi$ satisfying the Zachrisson equation
with unilateral constraints.

These two theorems obviously yield the following.

######  Corollary 3.4.

There exists the value of the one-side stopping Markov game.

Theorem 3.2 and 3.3 are proved in Sections 4 and 5 respectively.

##  4 Suboptimal strategies

To prove Theorem 3.2, we consider suboptimal strategies of the players. Let us
start with the construction of suboptimal strategy of the first player in the
one-side stopping Markov game.

Given a function $\phi\in\mathcal{AC}$, we define a strategy
$\hat{u}_{\phi}\in\mathcal{U}_{\operatorname{fb}}$ and a stopping rule
$\hat{\vartheta}_{\phi,t_{0}}\in\mathcal{T}_{\operatorname{fb}}$ by the rules:

$\hat{u}_{\phi}(t,i)\in\underset{u\in
U}{\operatorname{Argmin}}\Bigl{[}\sum_{j\in\mathcal{S}}Q_{i,j}(t,u,v)\varphi(t,j)+h(t,i,u,v)\Bigr{]},$
(5)
$\hat{\vartheta}_{\phi}(t,i)=\left\\{\begin{array}[]{cc}1,&\phi(t,i)=g(t,i),\\\
0,&\phi(t,i)\neq g(t,i).\end{array}\right.$

The latter corresponds to the following stopping time with values on the time
interval $[t_{0},T]$

$\hat{\tau}_{\phi,t_{0}}(\omega)=\bar{\tau}_{t_{0}}[\hat{\vartheta}_{\phi}](\omega)=\min\\{t\in[t_{0},T]:\phi(t,\omega(t))=g(t,\omega(t))\\}.$
(6)

######  Proposition 4.1.

Assume that $\varphi$ satisfies conditions (Z1), (Z3) of Definition 3.1. Then,
for every $t_{0}\in[0,T]$, $i_{0}\in\mathcal{S}$ and each
$\beta\in\mathcal{U}_{t_{0}}$, the following inequality holds true:

$\mathbb{E}^{\hat{u}_{\varphi},\beta}_{t_{0},i_{0}}G_{t_{0}}^{\hat{u}_{\varphi},\beta}(\hat{\tau}_{\varphi,t_{0}})\leq\varphi(t_{0},i_{0})$
(7)

###### Proof.

First, due to assumption (Z1), we have that the stopping time
$\hat{\tau}_{\varphi,t_{0}}$ takes values in $[t_{0},T]$.

By the optional sampling theorem [9, Theorem 7.29] and the facts that process
(2) with $\alpha=\alpha[\hat{u}_{\varphi}]$ is a
$(\mathbb{P}^{\hat{u}_{\varphi},\beta}_{t_{0},i_{0}},\mathbb{F}_{t_{0}})$-martingale,
while
$\mathbb{P}^{\hat{u}_{\varphi},\beta}_{t_{0},i_{0}}(\\{\omega:\omega(t_{0})=i_{0}\\})=1$,
we have that

$\begin{split}\varphi(t_{0},i_{0})=\mathbb{E}_{t_{0},i_{0}}^{\hat{u}_{\varphi},\beta}\bigg{[}\phi&(\hat{\tau}_{\varphi,t_{0}},\omega(\hat{\tau}_{\varphi,t_{0}}))-\int_{t_{0}}^{\hat{\tau}_{\varphi,t_{0}}}\Bigl{[}\frac{\partial}{\partial
t}\phi(t^{\prime},\omega(t^{\prime}))\\\
&+\sum_{j\in\mathcal{S}}Q_{\omega(t^{\prime}),j}(t^{\prime},\hat{u}_{\varphi}(t^{\prime},\omega(t^{\prime})),\beta(t^{\prime},\omega))\phi(t^{\prime},j)\Bigr{]}dt^{\prime}\bigg{]}.\end{split}$

The assumption that $\varphi$ satisfies condition (Z3) implies that

$\frac{\partial}{\partial
t}\varphi(t^{\prime},\omega(t^{\prime}))\leq-H(t^{\prime},\varphi(t^{\prime},\omega(t^{\prime})))$

for a.e. $t^{\prime}\in[t_{0},\hat{\tau}_{\varphi,t_{0}}(\omega)]$. This and
the definition of the stopping rule $\hat{\vartheta}_{\varphi}$ (that, in its
own turn, determines the stopping time $\hat{\tau}_{\phi,t_{0}}$ see (6)) give
that

$\begin{split}\varphi(t_{0},i_{0})\geq\mathbb{E}_{t_{0},i_{0}}^{\hat{u}_{\varphi},\beta}g(\hat{\tau}_{\varphi,t_{0}},\omega(\hat{\tau}_{\varphi,t_{0}}&))\\\
+\mathbb{E}_{t_{0},i_{0}}^{\hat{u}_{\varphi},\beta}\int_{t_{0}}^{\hat{\tau}_{\varphi,t_{0}}}&{}\Bigl{[}H_{i}(t^{\prime},\varphi(t^{\prime}))\\\
&-\sum_{j\in\mathcal{S}}Q_{\omega(t^{\prime}),j}(t^{\prime},\hat{u}(t^{\prime},\omega(t^{\prime})),\beta(t^{\prime},\omega))\phi(t^{\prime},j)\Bigr{]}dt^{\prime}.\end{split}$

Due to the definitions of $H_{i}$ (see (4)) and the strategy
$\hat{u}_{\varphi}$ (see (5)), we have that

$\begin{split}H_{i}(t^{\prime},\varphi(t^{\prime}))-\sum_{j\in\mathcal{S}}Q_{\omega(t^{\prime}),j}(t^{\prime},\hat{u}_{\varphi}(t^{\prime},&\omega(t^{\prime})),\beta(t^{\prime},\omega))\phi(t^{\prime},j)\\\
&\geq
h(t^{\prime},i,\hat{u}_{\varphi}(t^{\prime},\omega(t^{\prime})),\beta(t^{\prime},\omega)).\end{split}$

Therefore,

$\varphi(t_{0},i_{0})\geq\mathbb{E}_{t_{0},i_{0}}^{\hat{u}_{\varphi},\beta}\Bigl{[}g(\hat{\tau}_{\varphi,t_{0}},\omega(\hat{\tau}_{\varphi,t_{0}}))+\int_{t_{0}}^{\hat{\tau}_{\varphi,t_{0}}}h(t^{\prime},i,\hat{u}_{\varphi}(t^{\prime},\omega(t^{\prime})),\beta(t^{\prime},\omega))dt^{\prime}\Bigr{]}.$

Using the definition of the process $G$, we obtain inequality (7). ∎

Now we consider the second player’s suboptimal strategy $\tilde{v}$ that is
defined on the base of a function $\phi\in\mathcal{AC}$ as follows:

$\tilde{v}_{\phi}(t,i)\in\underset{v\in V}{\operatorname{Argmax}}\min_{u\in
U}\Bigl{[}\sum_{j\in\mathcal{S}}Q_{i,j}(t,u,v)\varphi(t,j)+h(t,i,u,v)\Bigr{]}.$
(8)

######  Proposition 4.2.

Let $\varphi\in\mathcal{AC}$ satisfy condition (Z2), (Z4). Then, for every
$t_{0}\in[0,T]$, $i_{0}\in\mathcal{S}$, $\alpha\in\mathcal{U}_{t_{0}}$,
$\tau\in\mathcal{T}_{t_{0}}$,

$\mathbb{E}_{t_{0},i_{0}}^{\alpha,\tilde{v}_{\varphi}}G_{t_{0}}^{\alpha,\tilde{v}_{\varphi}}(\tau)\geq\varphi(t_{0},i_{0}).$
(9)

###### Proof.

The proof is also by the verification arguments. Using the fact that process
(2) with $\phi=\varphi$ and $\beta=\beta[\tilde{v}_{\varphi}]$ is a
$(\mathbb{P}_{t_{0},i_{0}}^{\alpha,\tilde{v}_{\varphi}},\mathbb{F}_{t_{0}})$-martingale,
the equality
$\mathbb{P}_{t_{0},i_{0}}^{\alpha,\tilde{v}_{\varphi}}(\\{\omega:\omega(t_{0})=i_{0}\\})=1$
and optional sampling theorem [9, Theorem 7.29], we conclude that

$\begin{split}\varphi(t_{0},i_{0})=\mathbb{E}_{t_{0},i_{0}}^{\alpha,\tilde{v}_{\varphi}}\bigg{[}\varphi(&\tau,\omega(\tau))\\\
&-\int_{t_{0}}^{\tau}\Bigl{[}\frac{\partial}{\partial
t}\varphi(t^{\prime},\omega(t^{\prime}))+\sum_{j\in\mathcal{S}}Q_{\omega(t^{\prime}),j}(t,\alpha(t^{\prime},\omega),\tilde{v}(t^{\prime},\omega(t^{\prime})))dt^{\prime}\Bigr{]}\bigg{]}.\end{split}$

Applying conditions (Z2), (Z4), the definitions of the Hamiltonian (see (4))
and the strategy $\tilde{v}_{\varphi}$ (see (8)), we obtain the following
estimate:

$\varphi(t_{0},i_{0})\leq\mathbb{E}_{t_{0},i_{0}}^{\alpha,\tilde{v}_{\varphi}}\bigg{[}g(\tau,\omega(\tau))-\int_{t_{0}}^{\tau}h(t^{\prime},\omega(t^{\prime}),\alpha(t^{\prime},\omega),\tilde{v}_{\varphi}(t^{\prime},\omega(t^{\prime})))\bigg{]}.$

This gives the statement of the proposition. ∎

###### Proof of Theorem 3.2.

This theorem directly follows from Propositions 4.1, 4.2 and inequality (3). ∎

##  5 Existence of solution for the Zachrisson equation with unilateral
constraints

To prove the existence of the solution of the Zachrisson equation with
unilateral constraints, we consider the sequence of functions
$\varphi_{N}:[0,T]\times\mathcal{S}\rightarrow\mathbb{R}$ defined as follows.

First, we set $t^{k}_{N}\triangleq Tk/N$. Then, let

$\varphi_{N}(T,i)\triangleq g(T,i).$ (10)

Now, assume that the function $\varphi_{N}$ is already defined for all
$t\in[t^{k+1}_{N},T]$ and every $i\in\mathcal{S}$. Let
$\psi_{N}^{k}:[t^{k}_{N},t^{k+1}_{N}]\times\mathcal{S}\rightarrow\mathbb{R}$
solve the boundary value problem on $[t^{k}_{N},t^{k+1}_{N}]$:

$\frac{d}{dt}\psi_{N}^{k}(t,i)=-H_{i}(t,\psi_{N}^{k}(t)),\ \
\psi_{N}^{k}(t^{k+1}_{N},i)=\varphi_{N}(t^{k+1}_{N},i),\ \ i\in\mathcal{S}.$
(11)

Finally, set, for $t\in[t^{k}_{N},t^{k+1}_{N}]$,

$\varphi_{N}(t,i)\triangleq\psi_{N}^{k}(t,i)\wedge g(t,i).$ (12)

Now examine the properties of the sequence $\\{\varphi_{N}\\}_{N=1}^{\infty}$.

######  Lemma 5.1.

There exists a constant $C_{1}$ such that, for every natural $N$, $t\in[0,T]$,
$i\in\mathcal{S}$,

$|\varphi_{N}(t,i)|\leq C_{1}.$

###### Proof.

First, denote

$M_{Q}\triangleq\max\\{|Q_{i,j}(t,u,v)|:i,j\in\mathcal{S},\,t\in[0,T],\,u\in
U,\,v\in V\\},$ (13)
$M_{h}\triangleq\max\\{|h(t,i,u,v)|:t\in[0,T],\,i\in\mathcal{S},\,u\in
U,\,v\in V\\},$ (14)
$M_{g}\triangleq\max\\{|g(t,i)|:t\in[0,T],\,i\in\mathcal{S}\\}.$ (15)

Due to assumptions (H1), (H2), the quantities $M_{Q}$, $M_{h}$ and $M_{g}$ are
finite.

Put

$\mathcal{M}(t)\triangleq(M_{g}+M_{h}(T-t))e^{dM_{Q}(T-t)}.$ (16)

We will prove the estimate

$|\varphi_{N}(t,i)|\leq\mathcal{M}(t)$ (17)

by the backward induction.

By the definition of the function $\mathcal{M}$, (17) holds true at $t=T$.

Further, assume that (17) is fulfilled on $[t^{k+1}_{N},T]$. Let us show that
the functions

$\xi_{N}^{k}(t)\triangleq\max_{i\in\mathcal{S}}|\psi^{k}_{N}(t,i)|$ (18)

satisfies on $[t^{k}_{N},t^{k+1}_{N}]$ the following inequality:

$\xi_{N}^{k}(t)\leq\mathcal{M}(t).$ (19)

Indeed, by (11) and (4) we have that

$\xi^{k}_{N}(t)\leq\mathcal{M}(t^{k+1}_{N})+\int_{[t,t^{k+1}_{N}]}dM_{Q}\xi^{k}_{N}(t^{\prime})dt^{\prime}+M_{h}(t^{k+1}_{N}-t).$

Applying the Gronwall’s inequality and definition of the function
$\mathcal{M}$ (see (16)), we conclude that (19) holds true on
$[t^{k}_{N},t^{k+1}_{N}]$. The definition of $\varphi_{N}$ on
$[t^{k}_{N},t^{k+1}_{N}]$ (see (12)) and the fact that $g$ is bounded by
$M_{g}$, while $\mathcal{M}(t)\geq M_{g}$ yield estimate (17) on
$[t^{k}_{N},t^{k+1}_{N}]$.

To complete the proof, let

$C_{1}\triangleq\mathcal{M}(0).$

∎

######  Lemma 5.2.

If $k\in\\{0,\ldots,N-1\\}$, $s,r\in[t^{k}_{N},t^{k+1}_{N}]$, then

$|\psi^{k}_{N}(s,i)-\psi^{k}_{N}(r,i)|\leq C_{2}|s-r|,$

where $C_{2}$ is a constant depending only on $g$, $h$ and $Q$,

###### Proof.

Since $\psi_{N}^{k}$ satisfies ODE (11), it suffices to estimate the right-
hand side of this equation. First, due to the definition of the Hamiltonian
and the constants $M_{Q}$, $M_{h}$ (see (4), (13), (14)), we have that

$|H_{i}(t,\psi_{N}^{k})|\leq
dM_{Q}\max_{i\in\mathcal{S}}|\psi^{k}_{N}(t,i)|+M_{h}.$

Using the estimate of $\max_{i\in\mathcal{S}}|\psi^{k}_{N}(t,i)|$ by the
function $\mathcal{M}$ (see (18), (19)) and the fact that $\mathcal{M}(t)\leq
C_{1}$, we obtain the statement of the lemma with $C_{2}\triangleq
dM_{Q}C_{1}+M_{h}$. ∎

######  Lemma 5.3.

There exists a constant $C_{3}$ such that, for every natural $N$,
$s,r\in[0,T]$, $i\in\mathcal{S}$,

$|\varphi_{N}(s,i)-\varphi_{N}(r,i)|\leq C_{3}|s-r|.$ (20)

###### Proof.

Recall (see assumption (H3)) the function $g$ is Lipschitz continuous w.r.t.
the time variable. Let $L_{g}$ denote this Lipschitz constant. Put

$C_{3}\triangleq L_{g}\vee C_{2}.$ (21)

Further, let us consider time instants $t^{\prime},t^{\prime\prime}$ such that
they lies in the same time interval $[t^{k}_{N},t^{k+1}_{N}]$ for some $k$.
Without loss of generality, one can assume that
$\varphi_{N}(t^{\prime},i)>\varphi_{N}(t^{\prime\prime},i)$. To estimate
$|\varphi_{N}(t^{\prime},i)-\varphi_{N}(t^{\prime\prime},i)|=\varphi_{N}(t^{\prime},i)-\varphi_{N}(t^{\prime\prime},i)$,
we consider two cases.

  1. 1.

$\varphi_{N}(t^{\prime\prime},i)<g(t^{\prime\prime},i)$. Therefore,
$\varphi_{N}(t^{\prime\prime},i)=\psi_{N}^{k}(t^{\prime\prime},i)$, while
$\varphi_{N}(t^{\prime},i)\leq\psi_{N}^{k}(t^{\prime},i)$. The latter
inequality directly follows from the definition of the function $\varphi_{N}$
(see (12)). By Lemma 5.2, we have that

$\varphi_{N}(t^{\prime},i)-\varphi_{N}(t^{\prime\prime},i)\leq\psi^{k}_{N}(t^{\prime},i)-\psi_{N}(t^{\prime\prime},i)\leq
C_{2}|t^{\prime}-t^{\prime\prime}|\leq C_{3}|t^{\prime}-t^{\prime\prime}|.$

  2. 2.

$\varphi_{N}(t^{\prime\prime},i)=g(t^{\prime\prime},i)$. As above, by
definition of the function $\varphi_{N}$ (see (12)),
$\varphi_{N}(t^{\prime},i)\leq g(t^{\prime},i)$. Hence,

$\varphi_{N}(t^{\prime},i)-\varphi_{N}(t^{\prime\prime},i)\leq
g(t^{\prime},i)-g(t^{\prime\prime},i)\leq
L_{g}|t^{\prime}-t^{\prime\prime}|\leq C_{3}|t^{\prime}-t^{\prime\prime}|.$

Therefore, we derive (20) for $s,r$ lying in some interval
$[t^{k}_{N},t^{k+1}_{N}]$. To complete the proof it suffices to sum up
inequalities (20) on small time intervals. ∎

######  Lemma 5.4.

Let $t\in[0,T]$ and $i\in\mathcal{S}$ be such that $\phi_{N}(t,i)<g(t,i)$ and
$\varphi_{N}$ is differentiable at $t$. Then

$\frac{d}{dt}\phi_{N}(t,i)\leq-H_{i}(t,\varphi_{N}(t)).$ (22)

###### Proof.

First, let us consider the case where $t\in(t^{k}_{N},t^{k+1}_{N})$ for some
$k$. Due to the assumption that $\phi_{N}(t,i)<g(t,i)$, we have that

$\phi_{N}(t,i)=\psi_{N}^{k}(t,i).$

Moreover, the inequality $\phi_{N}(t^{\prime},i)<g(t^{\prime},i)$ holds in
some neighborhood of $t$. Thus,

$\frac{d}{dt}\phi_{N}(t,i)=\frac{d}{dt}\psi_{N}^{k}(t).$

By construction of the function $\psi_{N}^{k}$, we have that

$\frac{d}{dt}\varphi_{N}(t,i)=\frac{d}{dt}\psi_{N}^{k}(t)=-H_{i}(t,\psi_{N}^{k}(t)).$

Further, notice that $\varphi_{N}(t,j)\leq\psi_{N}^{k}(t,j)$,
$Q_{i,j}(t,u,v)\geq 0$ for $i\neq j$. This and the equality
$\phi_{N}(t,i)=\psi_{N}^{k}(t,i)$ imply that, for every $u\in U$ and $v\in V$,

$\sum_{j\in\mathcal{S}}Q_{i,j}(t,u,v)\varphi_{N}(t,j)+h_{i}(t,i,u,v)\leq\sum_{j\in\mathcal{S}}Q_{i,j}(t,u,v)\psi_{N}^{k}(t,j)+h_{i}(t,i,u,v).$
(23)

Therefore, using the definition of the Hamiltonian (see (4)), we obtain the
inequality

$H_{i}(t,\varphi_{N}(t))\leq H_{i}(t,\psi_{N}^{k}(t)).$

Combining this with (5), we conclude that (22) holds true for $t\neq
t^{k}_{N}$,

Now let us consider the case when $t=t^{k+1}_{N}$ for some $k$. By
construction of the function $\varphi_{N}$, we have that
$\varphi_{N}(t_{N}^{k+1})=\psi_{N}^{k}(t^{k+1}_{N})$. Additionally, due to the
assumption $\varphi_{N}(t_{N}^{k+1},i)<g(t_{N}^{k+1},i)$ and the continuity of
these functions, we conclude that $\varphi_{N}(t^{\prime},i)<g(t^{\prime},i)$
when $t^{\prime}\in(t_{N}^{k+1}-\delta,t_{N}^{k+1}]$. Hence, the construction
of the function $\varphi_{N}$ gives that
$\varphi_{N}(t^{\prime},i)=\psi_{N}^{k}(t^{\prime},i)$ on
$(t_{N}^{k+1}-\delta,t_{N}^{k+1}]$. Therefore,

$\frac{d}{dt}\varphi_{N}(t^{k+1}_{N},i)=\frac{d^{-}}{dt^{-}}\psi_{N}^{k}(t_{N}^{k+1},i)=-H_{i}(t_{N}^{k+1},\psi_{N}^{k-1}(t_{N}^{k+1})).$

Here $\frac{d^{-}}{dt-}$ stands for the left-hand derivative. This and (23)
yield that (22) holds true in the case when $t\in\\{t^{k}_{N}\\}_{k=1}^{N-1}$.
∎

######  Lemma 5.5.

There exists a constant $C_{4}$ such that, for every $s,r\in[0,T]$, $s<r$, and
$i\in\mathcal{S}$, the following inequality holds true:

$\varphi_{N}(r,i)-\varphi_{N}(s,i)\geq\int_{s}^{r}H_{i}(t,\varphi_{N}(t))dt-\frac{C_{4}}{N}$

###### Proof.

Let $m,n\in\\{0,\ldots,N-1\\}$ be such that $s\in[t^{m}_{N},t^{m+1}_{N})$,
$r\in(t^{n}_{N},t^{n+1}_{N}]$.

We have that

$\begin{split}\varphi_{N}(r,i)-\varphi_{N}(s,i)=\varphi_{N}(r,i)-\varphi_{N}(&t^{n}_{N})+\varphi_{N}(t^{m+1}_{N},i)-\varphi_{N}(s,i)\\\
&+\sum_{k=m+1}^{n-1}(\varphi_{N}(t^{k+1}_{N},i)-\varphi_{N}(t^{k}_{N},i))\\\
\geq\varphi_{N}(r,i)-\varphi_{N}(&t^{n}_{N})+\varphi_{N}(t^{m+1}_{N},i)-\varphi_{N}(s,i)\\\
&+\sum_{k=m+1}^{n-1}(\psi_{N}^{k}(t^{k+1}_{N},i)-\psi^{k}_{N}(t^{k}_{N},i)).\end{split}$

In the latter inequality, we used the definition of the functions
$\psi_{N}^{k}$ and $\varphi_{N}$ (see (11) and (12)). Further, due to Lemma
5.3,
$|\varphi_{N}(r,i)-\varphi_{N}(t^{n}_{N})|,\,|\varphi_{N}(t^{m+1}_{N},i)-\varphi_{N}(s,i)|\leq
C_{3}T/N$. Using this and the fact that each function $\psi^{k}_{N}(\cdot)$
satisfies (11), we conclude that, for each $k$,

$\varphi_{N}(r,i)-\varphi_{N}(s,i)\geq-2C_{3}\frac{T}{N}+\sum_{k=m+1}^{n-1}\int^{t^{k+1}_{N}}_{t^{k}_{N}}H_{i}(t,\psi_{N}^{k}(t))dt.$
(24)

By the equality $\psi_{N}^{k}(t_{N}^{k+1})=\varphi_{N}(t_{N}^{k+1})$, we have
that

$\begin{split}H_{i}(t,\psi_{N}^{k}(t))=H_{i}(t,\varphi_{N}(t))+(H_{i}&(t,\psi_{N}^{k}(t))-H_{i}(t,\psi_{N}^{k}(t_{N}^{k+1})))\\\
&+(H_{i}(t,\varphi_{N}(t_{N}^{k+1}))-H_{i}(t,\varphi_{N}(t))).\end{split}$

Lemmas 5.2, 5.3 and the fact that $H_{i}$ is Lipschitz continuous w.r.t. the
second variable with the constant $dM_{Q}$ give that, for
$t\in[t_{N}^{k},t^{k+1}_{N}]$,

$H_{i}(t,\psi_{N}^{k}(t))\geq
H_{i}(t,\varphi_{N}^{k}(t))-(C_{3}+C_{2})dM_{Q}\frac{T}{N}.$ (25)

Finally, using the definition of Hamiltonian (see (4)) and Lemma 5.1, we
conclude that

$|H_{i}(t,\varphi_{N}(t))|\leq C^{\prime}.$

Here $C^{\prime}$ is a constant dependent only on the examined game. This,
inequalities (24) and (25) and the fact that $r-t_{N}^{n},t^{m+1}_{N}-s\leq
T/N$ imply that

$\begin{split}\varphi_{N}(r,i)-\varphi_{N}(s,i)\geq-(3C_{3}+&C_{2}+C^{\prime})\frac{T}{N}+\int_{s}^{t^{m+1}_{N}}H_{i}(t,\varphi_{N}(t))dt\\\
&+\sum_{k=m+1}^{n-1}\int^{t^{k+1}_{N}}_{t^{k}_{N}}H_{i}(t,\varphi_{N}(t))dt+\int^{r}_{t^{n}_{N}}H_{i}(t,\varphi_{N}(t))dt\\\
=-(3C_{3}+&C_{2}+C^{\prime})\frac{T}{N}+\int_{s}^{r}H_{i}(t,\varphi_{N}(t))dt.\end{split}$

This gives the statement of the lemma.

∎

###### Proof of Theorem 3.3.

As it was mentioned above, to prove the existence of the Zachrisson equation
with unilateral constraints, we use the sequence of functions
$\\{\varphi_{N}\\}_{N=1}^{\infty}$. Due to Lemma 5.1, these functions are
uniformly bounded. Lemma 5.3 says that these functions are Lipschitz
continuous with the same constant. By the Arzela–Ascoli theorem, there exist a
sequence $\\{\varphi_{N_{l}}\\}_{l=1}^{\infty}$ and a function $\varphi$ such
that $\varphi_{N_{l}}\rightarrow\varphi$ as $l\rightarrow\infty$. The limiting
function $\varphi$ is bounded by the constant $C_{1}$ and is Lipschitz
continuous with the constant $C_{3}$. Hence,

$\varphi\in\mathcal{AC}.$

Further, by construction, each function $\varphi_{N_{l}}$ satisfies the
boundary condition

$\varphi_{N_{l}}(T)=g(T).$

Passing to the limit, we obtain that $\varphi$ satisfies condition (Z1).
Analogously, (12) implies that

$\varphi_{N_{l}}(t,i)\leq g(t,i),\ \ i\in\mathcal{S}.$

Therefore, condition (Z2) is fulfilled for the limiting function $\varphi$.

Let $i\in\mathcal{S}$ and let $t\in(0,T)$ be a point of differentiability of
the functions $\varphi(\cdot,i)$ such that $\varphi(t,i)<g(t,i)$. Choose
$\varepsilon$ satisfying

$3\varepsilon\leq g(t,i)-\varphi(t,i).$

Due to the continuity of the functions $g$ and $\varphi$, we have that there
exists $\delta>0$ such that, for $t^{\prime}\in(t-\delta,t+\delta)$,

$\varphi(t^{\prime},i)+2\varepsilon<g(t^{\prime},i).$

Using the fact that $\varphi_{N_{l}}\rightarrow\varphi$ as
$l\rightarrow\infty$, we have that, for sufficiently large $l$ and every
$t^{\prime}\in(t-\delta,t+\delta)$,

$\varphi_{N_{l}}(t^{\prime},i)+\varepsilon<g(t^{\prime},i).$

Lemma 5.4 implies that, if $\hat{t}\in(t-\delta,t+\delta)$,

$\varphi_{N_{l}}(\hat{t},i)-\varphi_{N_{l}}(t)\leq-\int_{t}^{\hat{t}}H_{i}(t^{\prime},\varphi_{N_{l}}(t^{\prime}))dt^{\prime}.$

Passing to the limit, we conclude that

$\varphi(\hat{t},i)-\varphi(t)\leq-\int_{t}^{\hat{t}}H_{i}(t^{\prime},\varphi(t^{\prime}))dt^{\prime}$

when $\hat{t}\in(t-\delta,t+\delta)$. Since $t\in(0,T)$ is a point of
differentiability of the function $\varphi(\cdot,i)$, we arrive at condition
(Z3).

To prove that $\varphi$ satisfies (Z4), notice that Lemma 5.5 implies that,
for every $s,r\in[0,T]$, $s<r$,

$\varphi_{N_{l}}(r)-\varphi_{N_{l}}(s)\geq-\int_{s}^{r}H_{i}(t,\varphi_{N_{l}}(t))dt-
C_{4}/N.$

Passing to the limit, we have

$\varphi(r)-\varphi(s)\geq-\int_{s}^{r}H_{i}(t,\varphi(t))dt.$

This gives condition (Z4) at every point of differentiability of the function
$\varphi$.

The uniqueness follows from Theorem 3.2. Indeed, each functions satisfying
(3.1) coincides with both upper and lower values.

∎

Acknowledgment.  The paper was prepared within the framework of the HSE
University Basic Research Program in 2022.

## References

  * [1] Y. V. Averboukh.  Approximation of value function of differential game with minimal cost.  Vestn. Udmurt. Univ.: Mat. Mekhanika Komp’yuternye Nauki, 31(4):536–561, 2021.
  * [2] E. N. Barron.  Differential games with maximum cost.  Nonlinear Anal. Theory Methods Appl., 14(11):971–989, 1990.
  * [3] E. B. Dynkin.  Game variant of a problem on optimal stopping.  Soviet Math. Dokl., 10:270–274, 1969.
  * [4] E. B. Frid.  The optimal stopping rule for a two-person markov chain with opposing interests.  Theory Probab. Appl., 14(4):713–716, 1969.
  * [5] M. K. Ghosh and K. S. M. Rao.  Zero-sum stochastic games with stopping and control.  Oper. Res. Lett., 35(6):799–804, 2007.
  * [6] X. Guo, O. Hernández-Lerma, and T. Prieto-Rumeau.  A survey of recent results on continuous-time Markov decision processes (with comments and rejoinder).  Top, 14(2):177–261, 2006.
  * [7] X. P. Guo and O. Hernández-Lerma.  Continuous-time Markov Decision Processes: Theory and Applications.  Springer, New York, 2009.
  * [8] M. Horiguchi.  Markov decision processes with a stopping time constraint.  Math. Methods Oper. Res., 53(2):279–295, 2001.
  * [9] O. Kallenberg.  Foundations of Modern Probability.  Springer, New York, 2021.
  * [10] N. N. Krasovskii and A. I. Subbotin.  Game-theoretical control problems.  Springer, New York, 1988.
  * [11] E. Mordecki.  Optimal stopping and perpetual options for Lévy processes.  Finance Stoch., 6:473–493, 2002.
  * [12] A. N. Shiryaev.  Optimal Stopping Rules.  Springer, New York, 2008.
  * [13] A. I. Subbotin.  Generalized solutions of first-order PDEs. The dynamical perspective.  Birkhauser, Boston, 1995.
  * [14] L. Zachrisson.  Markov games.  Ann. Math. Stud., 52:211–253, 1964.

Yurii Averboukh: | Higher School of Economics,
---|---
| 11 Pokrovsky Bulvar, Moscow, Russia;
| Krasovskii Institute of Mathematics and Mechanics
| 16 S. Kovalevskoi str., Yekaterinburg, Russia;
| e-mail:mailto:averboukh<EMAIL_ADDRESS>


There is substantial empirical evidence about the success of dynamic
implementations of Hamiltonian Monte Carlo (HMC), such as the No
U-Turn Sampler (NUTS), in many challenging inference problems but
theoretical results about their behavior are scarce.  The aim of
this paper is to fill this gap. More precisely, we consider a
general class of MCMC algorithms we call dynamic HMC. We show that
this general framework encompasses NUTS as a particular case, implying
the invariance of the target distribution as a by-product.  Second,
we establish conditions under which NUTS is irreducible and
aperiodic and as a corrolary ergodic.
Under conditions similar to the ones existing for HMC, we also show that NUTS is geometrically ergodic.
Finally, we improve existing convergence results for HMC showing that this method is ergodic without any
boundedness condition on the stepsize and the number of leapfrog
steps, in the case where the target is a perturbation of a Gaussian

[1]
Christophe Andrieu, Anthony Lee, and Sam Livingstone.
A general perspective on the Metropolis-Hastings kernel.
arXiv preprint arXiv:2012.14881, 2020.

[2]
Christophe Andrieu and Johannes Thoms.
A tutorial on adaptive MCMC.
Statistics and computing, 18:343–373, 2008.

[3]
Michael Betancourt.
A conceptual introduction to Hamiltonian Monte Carlo.
arXiv preprint arXiv:1701.02434, 2017.

[4]
Michael Betancourt, Simon Byrne, Sam Livingstone, and Mark Girolami.
The geometric foundations of Hamiltonian Monte Carlo.
Bernouilli, pages 2257–2298, 2017.

[5]
Wolf-Jürgen Beyn, Luca Dieci, Nicola Guglielmi, Ernst Hairer,
Jesús María Sanz-Serna, Marino Zennaro, and JM Sanz-Serna.
Markov chain Monte Carlo and numerical differential equations.
Current Challenges in Stability Issues for Numerical
Differential Equations: Cetraro, Italy 2011, Editors: Luca Dieci, Nicola
Guglielmi, pages 39–88, 2014.

[6]
Nawaf Bou-Rabee, Andreas Eberle, and Raphael Zimmer.
Coupling and convergence for hamiltonian monte carlo.
May 2018.

[7]
Nawaf Bou-Rabee and Jesús María Sanz-Serna.
Randomized Hamiltonian Monte Carlo.
The Annals of Applied Probability, 27(4):2159–2194, 2017.

[8]
Nawaf Bou-Rabee and Jesús María Sanz-Serna.
Geometric integrators and the Hamiltonian Monte Carlo method.
Acta Numerica, 27:113–206, 2018.

[9]
Jan M Brauner, Sören Mindermann, Mrinank Sharma, David Johnston, John
Salvatier, Tomáš Gavenčiak, Anna B Stephenson, Gavin Leech,
George Altman, Vladimir Mikulik, et al.
Inferring the effectiveness of government interventions against
Science, 371(6531):eabd9338, 2021.

[10]
Simon Byrne and Mark Girolami.
Geodesic Monte Carlo on embedded manifolds.
Scandinavian Journal of Statistics, 40(4):825–845, 2013.

[11]
Bob Carpenter, Andrew Gelman, Matthew D Hoffman, Daniel Lee, Ben Goodrich,
Michael Betancourt, Marcus Brubaker, Jiqiang Guo, Peter Li, and Allen
Stan: A probabilistic programming language.
Journal of statistical software, 76(1), 2017.

[12]
Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier.
Markov chains.
Springer, 2018.

[13]
Simon Duane, Anthony D Kennedy, Brian J Pendleton, and Duncan Roweth.
Hybrid Monte Carlo.
Physics letters B, 195(2):216–222, 1987.

[14]
Johannes Jisse Duistermaat and Johan AC Kolk.
Multidimensional real analysis I: differentiation, volume 86.
Cambridge University Press, 2004.

[15]
Alain Durmus and Éric Moulines.
On the geometric convergence for mala under verifiable conditions.
arXiv preprint arXiv:2201.01951, 2022.

[16]
Alain Durmus, Eric Moulines, and Eero Saksman.
On the convergence of Hamiltonian Monte Carlo.
The Annals of Statistics, April 2017.

[17]
Hong Ge, Kai Xu, and Zoubin Ghahramani.
Turing: a language for flexible probabilistic inference.
In International Conference on Artificial Intelligence and
Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary
Islands, Spain, pages 1682–1690, 2018.

[18]
Mark Girolami and Ben Calderhead.
Riemann manifold langevin and Hamiltonian Monte Carlo methods.
Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 73(2):123–214, 2011.

[19]
Mathias Harrer, Pim Cuijpers, Toshi A Furukawa, and David D Ebert.
Doing meta-analysis with R: A hands-on guide.
CRC press, 2021.

[20]
Matthew D Hoffman and Andrew Gelman.
The No-U-Turn sampler: Adaptively setting path lengths in
Hamiltonian Monte Carlo.
J. Mach. Learn. Res., 15(1):1593–1623, 2014.

[21]
Steven G Krantz and Harold R Parks.
A primer of real analytic functions.
Springer Science & Business Media, 2002.

[22]
Devadatta Kulkarni, Darrell Schmidt, and Sze-Kai Tsui.
Eigenvalues of tridiagonal pseudo-toeplitz matrices.
Linear {Algebra and its Applications}, 297:63–80, 1999.

[23]
Jun S Liu and Jun S Liu.
Monte Carlo strategies in scientific computing, volume 75.
Springer, 2001.

[24]
Samuel Livingstone, Michael F Faulkner, and Gareth O Roberts.
Kinetic energy choice in hamiltonian/hybrid monte carlo.
June 2017.

[25]
Kerrie L Mengersen and Richard L Tweedie.
Rates of convergence of the hastings and metropolis algorithms.
The annals of Statistics, 24(1):101–121, 1996.

[26]
Sean P Meyn and Richard L Tweedie.
Markov chains and stochastic stability.
Springer Science & Business Media, 2012.

[27]
Radford Neal.
Bayesian learning via stochastic dynamics.
Advances in neural information processing systems, 5, 1992.

[28]
Radford M. Neal.
MCMC using Hamiltonian Dynamics.
In Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng,
editors, Handbook of Markov chain Monte Carlo. Chapman & Hall/CRC
PRess, 2011.

[29]
Yurii Nesterov.
Primal-dual subgradient methods for convex problems.
Mathematical programming, 120(1):221–259, 2009.

[30]
Enrique Outerelo et al.
Mapping degree theory, volume 108.
American Mathematical Soc., 2009.

[31]
Gareth O Roberts and Richard L Tweedie.
Geometric convergence and central limit theorems for multidimensional
hastings and metropolis algorithms.
Biometrika, 83(1):95–110, 1996.

[32]
John Salvatier, Thomas V. Wiecki, and Christopher Fonnesbeck.
Probabilistic programming in Python using PyMC3.
PeerJ Computer Science, 2:e55, apr 2016.

[33]
Simon Byrne Samuel Livingstone, Michael Betancourt and Mark Girolami.
On the geometric ergodicity of Hamiltonian Monte Carlo.
Bernoulli, 25(4A):3109–3138, 2019.

[34]
Matthew R Schofield, Richard J Barker, Andrew Gelman, Edward R Cook, and
Keith R Briffa.
A model-based approach to climate reconstruction using tree-ring
Journal of the American Statistical Association,
111(513):93–106, 2016.

[35]
Chris Sherlock, Szymon Urbas, and Matthew Ludkin.
The apogee to apogee path sampler.
Journal of Computational and Graphical Statistics, to appear.

[36]
Charlie Tang, Nitish Srivastava, and Russ R Salakhutdinov.
Learning generative models with visual attention.
Advances in Neural Information Processing Systems, 27, 2014.

[37]
Rens van de Schoot, Sarah Depaoli, Ruth King, Bianca Kramer, Kaspar
Märtens, Mahlet G Tadesse, Marina Vannucci, Andrew Gelman, Duco Veen,
Joukje Willemsen, et al.
Bayesian statistics and modelling.
Nature Reviews Methods Primers, 1(1):1, 2021.

[38]
Zhaoxia Yu, Michele Guindani, Steven F Grieco, Lujia Chen, Todd C Holmes, and
Xiangmin Xu.
Beyond t test and ANOVA: applications of mixed-effects models for
more rigorous statistical analysis in neuroscience research.
Neuron, 110(1):21–35, 2022.

MK, MV and ES are supported by Academy of Finland (Finnish Centre of Excellence in Randomness and Structures, grants 346311 and 346305).

A.D. would like to thank the Isaac Newton Institute for Mathematical Sci- ences for support and hospitality during the programme The
mathematical and statistical foundation of future data-driven engineering when work
on this paper was undertaken. This work was supported by: EPSRC grant number