## 5 Finding the Optimal Policy \(\pi^{*}\) for the Problem
### Rounds of the Algorithm  
Let us first describe round 1, which consisted of the following four steps. Step 1.1. Calculate the elements of the first row of the matrix \(M_{1}\). In accordance with expression (4), we set \(j\) = 1 for all locations, calculated the parameters \(Q_{i,1}\) for all \(i\) = 1,..., \(N\), and wrote them as the corresponding elements \(m_{i,1}\) of the first row of the matrix \(M_{1}\). Step 1.2. The chatbot performed the first (preliminary) scan of each location one by one and extracted the relevant information from each location. With the chatbot being unreliable, the human user verified that the target information from the scanned-once locations was not satisfiable yet and hence assigned 1 to the number of unsuccessful checks for each location. Step 1.3. Determine the location \(i_{1}^{*}\) and scan it once more. Location \(i_{1}^{*}\) was chosen such that \(Q_{i_{1}^{*},1}\) = \(max_{i}\)\(Q_{i,1}\). Location \(i_{1}^{*}\) = \(\pi_{1}^{*}\) (for the second time) was scanned. If the human user was satisfied with the target information extracted now from the location \(\pi_{1}^{*}\) = \(i_{1}^{*}\), the partial satisfaction level \(F(\pi^{*})\) obtained so far was computed, where \(\pi^{*}\) = \(\{\pi_{1}^{*}\}\), and the search was terminated; \(Q_{i_{1}^{*},1}\) in cell (1, \(i_{1}^{*}\)) was highlighted in bold (see numerical example in Section 7). Otherwise, the number of unsuccessful scans for location \(i_{1}^{*}\) was increased by 1, i.e., set \(j_{2}(i_{1}^{*})\): = \(j_{1}(i_{1}^{*})\) + 1 = 2. Go to the next round, round 2. Let us now assume that the rounds 1,..., \(k\) (\(k\geq 1\)) were completed, and the locations \(\pi^{*}_{1}\),..., \(\pi^{*}_{k}\) were determined at these rounds, i.e., the optimal subsequence \(\pi_{k}^{*}\) = (\(\pi_{1}^{*}\),\(\pi_{2}^{*}\),..., \(\pi_{k}^{*}\)) was found. At the end of the \(k\)th round, all parameters \(Q_{i,j}\), \(i\) = 1,..., \(N\), \(j\) = 1,2,..., and \(k+1\) were calculated and represented as a known (\(k+1\)) \(\times\)\(N\)-matrix \(M_{(k+1)}\). Accordingly, the corresponding indices \(j_{1}(i_{1}^{*})\), \(j_{2}(i_{2}^{*})\),..., and \(j_{k}(i_{k}^{*})\) and the objective function \(F(\pi^{*})\) were calculated. Then, the next, (\(k+1\))th round was as follows. In round \(k+1\), \(k\) = 1, 2,..., consisted of the following three steps. Step \(k+1.1\). Determine the location \(i_{(k+1)}^{*}\) to be scanned (\(k+1\))th-in-turn by the iterative algorithm. The second index \(j\) in the elements of the \((k+1)\)th row of the matrix \(M_{k+1}\) by \(j_{k+1}(i)\) for all \(i\) was determined; among all parameters \(Q_{i,j_{k+1}(i)}\), the location \(i^{*}\)\(k_{+1}\) (to be scanned as the next one) was selected, which had the maximum \(Q_{i,j_{k+1}(i)}\) as follows: \(Q_{i_{k+1},\,j_{k+1}}=max_{i=1,\ldots,N}\ Q_{i,j_{k+1}(i)}\). The item \(Q_{i^{*}_{k+1},\,j_{k+1}}\) was placed in cell \((k+1,\,i^{*}_{k+1})\) of the \((k+1)\)th row of the matrix \(M_{k+1}\), and this item was highlighted in bold. Step \(k+1.2\). The human user checked whether the location \(i^{*}_{k+1}\) contained the required target information; if yes, the search stopped; otherwise, the number of failed checks for location \(i^{*}_{k+1}\) was increased by \(1\). A current optimal subsequence \(\boldsymbol{\tau^{*}}=\boldsymbol{\pi^{*}}_{k+1}\) was considered, which, for now, was \(\boldsymbol{\pi^{*}_{bek+1}}^{*}=(\boldsymbol{\pi^{*}_{1}},\boldsymbol{\pi^{*} _{2}}\ldots,\boldsymbol{\pi^{*}_{k+1}})\); the efficiency \(F(\boldsymbol{\pi^{*}_{k+1}})\) was computed. The number of unsuccessful scans of location \(\boldsymbol{\pi^{*}_{k+1}}\) increased by \(1\), that is, the second index for location \(\boldsymbol{\pi^{*}_{k+1}}\) was changed as follows: \(j_{k+2}(\boldsymbol{\pi^{*}_{k+1}}):=j_{k+1}(\boldsymbol{\pi^{*}_{k+1}})+1\), leaving the second indices for all other locations unchanged: \(j_{k,k+2}:=j_{k,k+1}\), \(i\
eq i^{*}_{k+1}\). Go to step \(k+1.3\). Step \((k+1).3\). Determine all elements \(Q_{i,j}\) in the \((k+2)\)th row of matrix \(M_{k+2}\).