SSA Calls

At a given time LEFT's current stack will be either empty or of the form $Block_1$, $Block_2, \ldots, Block_u$, where $Block_i$ ( $i \in \{1, \ldots, u \}$) is of the form

$$[ v_i, RL(v_i), (c_i^1,{\sc Left }_{c_i^1}), (c_i^2,{\sc Left }_{c_i^2}), \ldots ].$$

Here $v_i$ denotes the $i$-th checkpoint still in LEFT's stack (compare section refis), $RL(v_i)$ denotes LEFT's reward until time $v_i$, $c_i^k$ ( $k \in \{1,2, \ldots, \}$) is the address of the $k$-th LEFT-column modified in between $v_i$ and the subsequent checkpoint, and ${\sc Left }_{c_i^k}$ is the corresponding previous LEFT-column. The pairs $(c_i^k,{\sc Left }_{c_i^k})$ were saved on the stack by the first LI that changed the corresponding LEFT-columns after $v_i$.

The procedures SSALEFT() and SSARIGHT() below will be invoked by module-modifying instructions to be discussed later.

SSALEFT():

1.

If BlockSSALEFT $=$ TRUE then exit. Else:

2.

Set BlockSSALEFT $=$ TRUE. Set variable $t$ equal to current time ($t$ is a new checkpoint). Use backtracking and the information in Stack${\sc Left }$ to undo as many of the most recent ${\sc Left }$-modifications as necessary to achieve SSC -- see inequality (1) in section 3. Pop off the corresponding blocks in Stack${\sc Left }$. This procedure guarantees that SSC will eventually be satisfied -- see, for example, [35].

3.

Push $t$ and $RL(t)$ onto Stack${\sc Left }$. They are the first two elements of the next block to be pushed.

SSARIGHT() is analogous to SSALEFT().

Back to Active Learning - Exploration - Curiosity page