Large Language Models (LLMs) are increasingly capable but often require significant guidance or extensive interaction history to perform effectively in complex, interactive environments, partly due to the "black box" nature of their internal reasoning. Existing methods may struggle with adapting to new information or efficiently utilizing past experiences for multi-step reasoning without fine-tuning. We introduce a novel LLM agent framework that enhances planning capabilities through in-context learning, facilitated by augmentation with learned programmatic atomic facts (structured textual statements) and a recursive lookahead search. Our agent learns to extract task-critical "atomic facts" from its interaction trajectories. These facts, serving as a form of programmatic representation, dynamically augment the prompts provided to LLM-based components responsible for action proposal, latent world model simulation (akin to using programs as environment models), and state-value estimation. Planning is performed via a depth-limited lookahead search, where the LLM simulates potential trajectories and evaluates their outcomes, guided by these accumulated programmatic facts and interaction history. This approach allows the agent to improve its understanding and decision-making online. By representing experience as a set of programmatic facts, the agent refines its behavior in-context, enhancing interpretability and efficiency without weight updates. We provide a theoretical motivation linking performance to the quality of fact-based abstraction and LLM simulation accuracy. Empirically, our agent demonstrates improved performance and adaptability on challenging interactive tasks, achieving more optimal behavior as it accumulates experience-grounded programmatic knowledge, showcased in tasks such as TextFrozenLake and ALFWorld.