Learn By Doing will always seem gamey, because it is the definition of gamey. Because the vast majority of people do not actually learn by doing. They learn through teaching. - First, they are taught by their family. Then by their family and teachers. Then by teachers and friends. Then by mentors at work (or through books and computers, if they're a nerd). Always, there is the expert teaching the skill. First people are taught, then they practice what they are taught in a controlled environment, then they go off and implement what they've learned in a real situation. Very rare is the individual who learns spontaneously, who invents a way to use a skill purely through trial and error.
All of which may seem familiar, however vaguely. Because this is a thing occasionally discussed in education, so you may have heard it in your younger days. And it also means LBD runs counter to common experience. With running counter to common experience being a hard road to trod, since you are defining the unfamiliar thing that is rpg rules with tools that are themselves unfamiliar to common experience. And defining something unfamiliar with something else that is also unfamiliar, of course, being no definition at all.
Howsoever, in game logic, the main trouble for the functionality of LBD has always been the open use skills (things that are used whenever the Player wants), not the closed use skills like combat. Combat skills are generally functional under LBD, if unintuitive. It's things like Stealth that cause LBD to break down. When does a Player get an xp tick for Stealth? Every creature they stealth past? What about civilians? Every time they stealth past a creature? What if they're going back and forth? And if you answer no to that, why not? Why is sneaking in to get the treasure a legit use of the skill, but sneaking out is not? How many xp ticks do you give to non-thief characters who do use stealth, such as rangers, in order to keep their stealth of a concurrent level with the rising game difficulty? And so on.
All of that said, in a game with a completely closed environment, where there is a fixed number of skill uses, such as can be implemented in CYOA, none of the above actually matters. Because you are utilizing your character in the game not through concurrent action in the game world, but through a fixed framework of set actions. If you CYOA the whole thing, you can actually count the exact number of skill uses there will be in the game. And so, it's no longer a question of when is Stealth on and is it a legit moment for it to be on to get the xp? Instead, it becomes - this is the situation, do you use Stealth or do you use Diplomacy, and per that choice get an xp check mark. Under that set of rules, LBD works just fine, and it works because it is utilizing the normal rules of CYOA to define its use.