Large Language Models (LLMs) excel when a solution can be planned from the prompt, but many sequential decision-making tasks require actions to depend on observations acquired during interaction. We study two central challenges in this regime: learning reusable interaction policies for history-dependent search, and acting under partial observability when task-relevant state is revealed only through interaction. We instantiate these challenges with two diagnostic benchmarks: Calc-Bench for reusable, history-dependent tool interaction, and partially observed sorting for action selection under hidden state. We introduce the Expanded Action space (ExpA), which decouples language reasoning from environment interaction by adding routing and environment-specific actions beyond vocabulary tokens. ExpA is trained with EARL, an RL algorithm using counterfactual policy optimization to explore rarely invoked but useful actions. EARL improves Countdown by 26.3% with 3B models and achieves perfect Sort-4 accuracy while discovering an efficient sorting strategy, providing a proof-of-concept for learned non-language interaction in controlled sequential decision-making diagnostics.