First-Order Definable Policies

Which finite-state reactive agents can have their action rules expressed in first-order logic over observation histories?In my previous post, I used Mealy machines to describe finite-state reactive agents. Here we want to ask which policies can be described using first-order logic. I will first explain what this logic can say about a finite observation history, then connect it to the policies. This post reviews the literature on first-order definability and finite automata and explains how the c...