Configuration space is a fixed set of knobs. Think of a form with dropdowns: learning rate from a list, batch size from a list, number of layers from a list. You define the options. The search picks among them.
Program space is the space of all valid programs. Your agent can write any code that runs. It could replace AdamW with a custom optimizer or add a regularization technique that didn't exist in your original search space. The difference: configuration space is bounded by what you anticipated. Program space is bounded only by what compiles and runs.