Partially observable Markov Decision Processes (POMDPs) are a standard model
for agents making decisions in uncertain environments. Most work on POMDPs
focuses on synthesizing strategies based on the available capabilities.
However, system designers can often control an agent's observation
capabilities, e.g. by placing or selecting sensors. This raises the question of
how one should select an agent's sensors cost-effectively such that it achieves
the desired goals. In this paper, we study the novel optimal observability
problem OOP: Given a POMDP M, how should one change M's observation
capabilities within a fixed budget such that its (minimal) expected reward
remains below a given threshold? We show that the problem is undecidable in
general and decidable when considering positional strategies only. We present
two algorithms for a decidable fragment of the OOP: one based on optimal
strategies of M's underlying Markov decision process and one based on parameter
synthesis with SMT. We report promising results for variants of typical
examples from the POMDP literature.

针对部分可观察的马尔可夫决策问题 (POMDPs)，本文研究了一种新颖的最优可观测性问题 (OOP)：如何在固定预算下选择一种代理人的传感器，使其达到预期目标。研究表明该问题在一般情况下是不可判定的，而考虑位置策略时是可判定的。我们提出了两种算法解决可判定的 OOP 问题：一种基于 M 的潜在马尔可夫决策过程的最优策略，另一种基于 SMT 的参数合成。我们对 POMDP 文献中的典型示例的变体进行了实验，并获得了有希望的结果。

POMDP 中最优奖励应观察什么？

What should be observed for optimal reward in POMDPs?

Motivated by applications in declarative data analysis, we study
$\mathit{Datalog}_{\mathbb{Z}}$---an extension of positive Datalog with
arithmetic functions over integers. This language is known to be undecidable,
so we propose two fragments. In $\mathit{limit}~\mathit{Datalog}_{\mathbb{Z}}$
predicates are axiomatised to keep minimal/maximal numeric values, allowing us
to show that fact entailment is coNExpTime-complete in combined, and
coNP-complete in data complexity. Moreover, an additional $\mathit{stability}$
requirement causes the complexity to drop to ExpTime and PTime, respectively.
Finally, we show that stable $\mathit{Datalog}_{\mathbb{Z}}$ can express many
useful data analysis tasks, and so our results provide a sound foundation for
the development of advanced information systems.

研究了正 Datalog 上添加整数算术函数的扩展语言 Datalog_Z，并提出了两个限制子语言 limit Datalog_Z 和 stable Datalog_Z 以解决其不可判定性，并证明了相应的 NP 完全性和 ExpTime 完全性，最终表明稳定的 Datalog_Z 能够表达许多有用的数据分析任务，为先进信息系统的发展提供了一个坚实的基础。