What is a state variable?

[Warren Powell]

Friends and colleagues (with apologies for cross postings)...

For a number of years I have been astonished by the number of papers that refer to a "state variable", or "the state of the system", without defining what a state variable is (this is not true of all communities, but it seems to be universally true in operations research). Top books (and Wikipedia) have definitions that parallel "The state variable is a set of parameters that describe the state of the system."

In 2012 I ran an NSF workshop on AI/OR where I asked everyone to offer their own definition.  I have edited this list, and then added a few definitions drawn from the literature.

I have compiled these on a spreadsheet, and I would like to invite you to rate these definitions (you don't have to rate all of them).  In addition, you may provide your own definition.  The spreadsheet is available at

http://tinyurl.com/whatisastatevariable

 Please share this with any colleagues that you think might be interested.  After a few weeks I will compile and share the results.

------------------------------

Warren B. Powell

Professor Emeritus, Princeton University

http://www.castlelab.princeton.edu

[Aditya Mahajan]

Dear Warren:

There is a rich literature on formal definitions of state in Systems and Control. Perhaps, the most commonly used definition for fully observed continuous time systems is presented by Willems in his 1972 paper on dissipative dynamical systems (https://link.springer.com/article/10.1007/BF00276493). For general, partially observed models, an accessible exposition is provided by Witsenhausen in his 1976 paper on some remarks on the concept of state (https://link.springer.com/chapter/10.1007/978-1-4684-2259-7_6), where he also points out to the relation with the definition of state due to Nerode (1958) used in automata theory. In the conclusion of that paper, Witsenhausen gives a colloquial (but precise) definition:

> The state should be a summary ("compression") of some data (the "past") known to someone (an observer or a controller) and sufficient for some purpose (input-output map, optimization, dynamic programming).

[I would change to say that "The state should be **a recursively updatable** summary..."]

This definitions hints at the fact that the state for input-output mapping may be different than the state for dynamic programming (think of an even MDP, where "absolute value of state" is sufficient for DP but not for input-output mapping). This is also reflected in your list where some definitions define state in terms of input-output mappings while other define in terms of control.

We provided a brief historic overview of the different definitions of states (for general partially observed models) in our recent paper on approximate information state: https://arxiv.org/abs/2010.08843

See Sec 2.3 for a definition of information state, Sec. 2.4 for various examples, and Sec 2.5 for the relationship with other definitions of state (primarily for partially observable models).

Best wishes,
Aditya

--
Aditya Mahajan | Associate Professor, ECE, McGill University
http://www.cim.mcgill.ca/~adityam | Ph: (514)-398-8088

> http://www.castlelab.princeton.edu<http://www.castlelab.princeton.edu/>
>
> --
> You received this message because you are subscribed to the "Reinforcement Learning Mailing List" group.
> To post to this group, send email to rl-...@googlegroups.com
> To unsubscribe from this group, send email to
> rl-list-u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/rl-list?hl=en
> ---
> You received this message because you are subscribed to the Google Groups "Reinforcement Learning Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to rl-list+u...@googlegroups.com<mailto:rl-list+u...@googlegroups.com>.
> To view this discussion on the web visit https://groups.google.com/d/msgid/rl-list/CA%2BS_GWJ50f_ZXqCY9s2Winvux7oCL9jFCzLbHVawpx0e1Q1ZiQ%40mail.gmail.com<https://groups.google.com/d/msgid/rl-list/CA%2BS_GWJ50f_ZXqCY9s2Winvux7oCL9jFCzLbHVawpx0e1Q1ZiQ%40mail.gmail.com?utm_medium=email&utm_source=footer>.
>

[Dimitri Bertsekas]

"Witsenhausen gives a colloquial (but precise) definition: 

> The state should be a summary ("compression") of some data (the "past") known to someone (an observer or a controller) and sufficient for some purpose (input-output map, optimization, dynamic programming)."

Yes Witsenhausen has it exactly right! This is the one definition I have been using in all my DP books.

Dimitri Bertsekas

[David Poole]

> On Jan 14, 2021, at 11:46 PM, Dimitri Bertsekas <dpber...@gmail.com> wrote:
>
> [CAUTION: Non-UBC Email]"Witsenhausen gives a colloquial (but precise) definition:

>
> > The state should be a summary ("compression") of some data (the "past") known to someone (an observer or a controller) and sufficient for some purpose (input-output map, optimization, dynamic programming)."
>
> Yes Witsenhausen has it exactly right! This is the one definition I have been using in all my DP books.
>

I’m surprised that you don’t (just) rely on the Markov condition:
The state at some time is information that renders statements about the past conditionally independent of statements about the future. If S_t is state at time t, and B is a statement about a previous time (before t) and A is a statement about a subsequent time (after t), then A is independent of B given S_t.

Or is that implicit in your definition? Is your definition more or less than this?

David

——
David Poole,
Department of Computer Science,
University of British Columbia,
https://cs.ubc.ca/~poole
po...@cs.ubc.ca

> To unsubscribe from this group and stop receiving emails from it, send an email to rl-list+u...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/rl-list/66b33b77-0af7-4069-aaa9-11f0b69be0a2n%40googlegroups.com.