We study the computational tractability of PAC reinforcement learning with
rich observations. We present new provably sample-efficient algorithms for
environments with deterministic hidden state dynamics and stochastic rich
observations. These methods operate in an oracle model of computation --
accessing policy and value function classes exclusively through standard
optimization primitives -- and therefore represent computationally efficient
alternatives to prior algorithms that require enumeration. With stochastic
hidden state dynamics, we prove that the only known sample-efficient algorithm,
OLIVE, cannot be implemented in the oracle model. We also present several
examples that illustrate fundamental challenges of tractable PAC reinforcement
learning in such general settings.

本文研究了 PAC 强化学习在富观察力下的计算复杂度，提出了基于确定性隐藏状态动态和随机富观察的可证明的样本有效算法，同时证明了在具有随机隐藏状态动态的情况下，已知样本有效算法 OLIVE 不能在 Oracle 模型中实现，通过几个示例表明了在这样一般的设置中可计算 PAC 强化学习的根本挑战。

使用丰富观察的 Oracle 有效 PAC RL

On Oracle-Efficient PAC RL with Rich Observations

Recurrent neural networks, and in particular long short-term memory (LSTM)
networks, are a remarkably effective tool for sequence modeling that learn a
dense black-box hidden representation of their sequential input. Researchers
interested in better understanding these models have studied the changes in
hidden state representations over time and noticed some interpretable patterns
but also significant noise. In this work, we present LSTMVIS, a visual analysis
tool for recurrent neural networks with a focus on understanding these hidden
state dynamics. The tool allows users to select a hypothesis input range to
focus on local state changes, to match these states changes to similar patterns
in a large data set, and to align these results with structural annotations
from their domain. We show several use cases of the tool for analyzing specific
hidden state properties on dataset containing nesting, phrase structure, and
chord progressions, and demonstrate how the tool can be used to isolate
patterns for further statistical analysis. We characterize the domain, the
different stakeholders, and their goals and tasks.

本文介绍了 LSTMVIS，一种用于理解循环神经网络（尤其是长短时记忆网络）隐藏状态动态的可视化分析工具，可通过结构性注释和大数据集对状态变化进行匹配和对齐，来分析论述特定的隐藏状态特性和模式。