wildbill:
Do you have proportional control of the valve or just open or closed?
The OP has not answered that. Assuming that it is on/off control, that the heating water is always at the same temperature, and that there is a big initial temperature difference between the actual and desired room temperatures I think the Arduino should be able to turn the radiator on, 'plot' the rate of change of room temperature and switch off so that the target is hit with acceptable accuracy.
Once the room is at the target temperature it is not going to be desirable to have the valve continuously opening and closing though, so there is going to have to some acceptable temperature band around the target temperature.
Knowing the outside temperature would help to tune things. However I think knowing the humidity of the air would also be an important factor. Damp air is going to take a lot more energy/time to heat than dry air.