In standard reinforcement learning, the action set is assumed to be known in advance, which means any forbidden state-action pairs must be identified before computation begins. Reboul, Croissant, and Halconruy isolate the case where computing this so-called action mask is itself the main bottleneck. They study a linear MDP model in which each attempted action reveals the exact value of a linear score that determines whether the action is valid.
The authors first construct an algorithm based on deterministic optimistic optimization. They show it is minimax optimal and computationally efficient, but also that it is suboptimal on non-degenerate instances. To address that gap, they propose an alternative algorithm that deliberately plans its exploration strategy. This second method admits a formal interpretation as an analogue of information-directed sampling adapted to deterministic feedback.
The paper also applies the framework to transfer learning, where the invalid action set changes over time. Because the mask is learned rather than assumed fixed, the approach offers a way to reuse knowledge when the set of permissible actions shifts between tasks.