I see some conflicting pieces of information.
just simple walking or balance
Balance is not simple. A balancing wheeled robot is a challenging project. Very doable, but a challenge.
A balancing walking robot is much more involved.
But the videos you linked to are not balancing robots. They are 4 or 6 legged walkers. They are all robots that are capable of walking.
I think that your starting point should be like what they started with. A robot capable of walking. To make that, you need to make a walking robot. After you have that, then take out the part that knows how to walk and put in your learning algorithm.
Pick a model. It can be a kit or you can make your own. Learn enough about the arduino to make the servos move. Use that to write code to make the model walk. This is a very important step. It confirms that your design is capable of walking. It confirms that the servos are strong enough to lift the model off the ground (not always a given). It confirms that your power supply will be usable in your genetic experiments.
Then take out the walking knowledge and put in your genetic piece. I will admit that I do not know what is involved in this step. But I assume that is what you want to experiment with.