Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions.
Backward induction is used to solve Bellman equations in dynamic programming, which is leveraged in reinforcement learning.
The markov property holds of a process if the probability of each event depends only on the state attained in the previous event, formally if P(st+1)=f(st) for some f.
For an example of a human approximating backward induction, I'll use the chocolate example from Instrumental and Terminal Values: Alice wants chocolate, so she computes that she needs to go to the store, so she computes that she needs to drive, so she computes that she needs to grab her keys. If it's not obvious how grabbing keys is related to obtaining chocolate, it should be obvious when you look a the whole chain.
Formally perhaps we might say for any goal An we can compute a list A1←A2←...←An−1←An, where A←B denotes "A leads to B and we can compute that fact from looking at B" or "from the desire for B we can compute the desire for A".
But! As Eliezer points out, if you're at the Agrabkeys←Adrive step, and an oracle tells you that the store is out of chocolate, you're not forced into some semi-myopia where you feel the need to start driving but you no longer know why. Instead, the whole chain might collapse at once, radically reconfigure itself from the initial desire for chocolate.
I feel like there's this possibility for a wrong interpretation of backward induction that's analogous to the markov property, where every desire in the chain is a function of the preceding desire to which it is instrumental. This wrong interpretation actually lies precisely in a blindspot of my previous formalization! Put much better, though a little difficult on the eyes:
Formally perhaps we might say that for any goal An we can compute a list of shrinking lists A1←(A2,...,An)←(A3,...,An)←...←(An−1,An)←An, where Ak←(Ak+1,...,An) denotes "Ak leads to Ak+1, which we can compute by looking at the sequence (Ak+1,...,An), (notice recursion, base case An−1←An)" or "from a desire for the list (Ak+1,...,An) we can compute the desire for Ak".
This formalism is robust to disruptions in the chain mid-planning, because the whole chain is input to compute a preceding instrumental goal.
So I have a basic belief about this, and I want to find a way to verify if it's true: Is it the case, when you're approximating backward induction IRL, that as you traverse from right to left you're gaining information? That is, every desire toward the left carries with it not only information about the desire immediately to it's right but also about the entire rest of the list up to the base case / terminal value, as in the second formalism?
Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions.
Backward induction is used to solve Bellman equations in dynamic programming, which is leveraged in reinforcement learning.
The markov property holds of a process if the probability of each event depends only on the state attained in the previous event, formally if P(st+1)=f(st) for some f.
For an example of a human approximating backward induction, I'll use the chocolate example from Instrumental and Terminal Values: Alice wants chocolate, so she computes that she needs to go to the store, so she computes that she needs to drive, so she computes that she needs to grab her keys. If it's not obvious how grabbing keys is related to obtaining chocolate, it should be obvious when you look a the whole chain.
Formally perhaps we might say for any goal An we can compute a list A1←A2←...←An−1←An, where A←B denotes "A leads to B and we can compute that fact from looking at B" or "from the desire for B we can compute the desire for A".
But! As Eliezer points out, if you're at the Agrabkeys←Adrive step, and an oracle tells you that the store is out of chocolate, you're not forced into some semi-myopia where you feel the need to start driving but you no longer know why. Instead, the whole chain might collapse at once, radically reconfigure itself from the initial desire for chocolate.
I feel like there's this possibility for a wrong interpretation of backward induction that's analogous to the markov property, where every desire in the chain is a function of the preceding desire to which it is instrumental. This wrong interpretation actually lies precisely in a blindspot of my previous formalization! Put much better, though a little difficult on the eyes:
Formally perhaps we might say that for any goal An we can compute a list of shrinking lists A1←(A2,...,An)←(A3,...,An)←...←(An−1,An)←An, where Ak←(Ak+1,...,An) denotes "Ak leads to Ak+1, which we can compute by looking at the sequence (Ak+1,...,An), (notice recursion, base case An−1←An)" or "from a desire for the list (Ak+1,...,An) we can compute the desire for Ak".
This formalism is robust to disruptions in the chain mid-planning, because the whole chain is input to compute a preceding instrumental goal.
So I have a basic belief about this, and I want to find a way to verify if it's true: Is it the case, when you're approximating backward induction IRL, that as you traverse from right to left you're gaining information? That is, every desire toward the left carries with it not only information about the desire immediately to it's right but also about the entire rest of the list up to the base case / terminal value, as in the second formalism?